RoughStrings
SRM 394 · 2008-03-22 · by Xixas
Problem Statement
Given a string s, its roughness is calculated as follows: Let c1 be the letter that appears most frequently in s, and let c2 be the letter that appears least frequently (c2 must appear at least once). The roughness of s is the number of occurrences of c1 minus the number of occurrences of c2.
You are allowed to modify s by erasing between 0 and n characters, inclusive (see example 1 for clarification). Return the minimum possible roughness that can be achieved by such a modification.
Constraints
- s will contain between 1 and 50 characters, inclusive.
- s will contain only lowercase letters ('a'-'z').
- n will be between 0 and m-1, inclusive, where m is the number of characters in s.
"aaaaabbc" 1 Returns: 3
We may remove one 'a' or one 'c' to obtain the minimal roughness of 3.
"aaaabbbbc" 5 Returns: 0
One of the ways is to remove 'c' and all occurrences of 'a'.
"veryeviltestcase" 1 Returns: 2
"gggggggooooooodddddddllllllluuuuuuuccckkk" 5 Returns: 3
"zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz" 17 Returns: 0
"bbbccca" 2 Returns: 0
Sometimes you may want to remove less than n characters.
Submissions are judged against all 211 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RoughStrings with a public method int minRoughness(string s, int n) · 211 test cases · 2 s / 256 MB per case