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.
Definition
- Class:
- RoughStrings
- Method:
- minRoughness
- Parameters:
- String, int
- Returns:
- int
- Method signature:
- int minRoughness(String s, int n)
- (be sure your method is public)
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.
Examples
"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.
"abcdeefzzzzzzzzzzzzzzzz"
6
Returns: 9
"vvnavgnaaagvanavvvvvvvvavavaavvvavvavvavvvgvav"
0
Returns: 23
"jjtvjjjjjjjvjjvjjjvvjjkjvvvvvjj"
5
Returns: 6
"mhmtbtbttttshthstttbmhttbht"
5
Returns: 6
"ffffffffffffffrrffffwfffffffffcff"
5
Returns: 0
"wwwuwuwwwwwwwuwwwuwuwwwwwywwuuuwuugwgwwwwwwwwugwrw"
3
Returns: 30
"ddandjgjdjddjdddjjdajdddddd"
5
Returns: 8
"kwccibibkbbckcckk"
1
Returns: 3
"tewe"
2
Returns: 0
"ehhhhjmememhhhhemehehehhhhememmhhh"
5
Returns: 6
"amaakaakkkakamaakaaaamaakk"
10
Returns: 0
"aaaaaaaaaaaaama"
3
Returns: 0
"zboozzvbbj"
7
Returns: 0
"ezzeazzzzzzazzazazzzzzzezzzzzazzzevzazze"
10
Returns: 14
"oooododofddododdddddddddoodfoodddoddddd"
10
Returns: 3
"ffffbffffffdbffffffbdfffffffkf"
10
Returns: 0
"vooooovv"
5
Returns: 0
"zzzzqz"
3
Returns: 0
"xxixisxigxxsss"
1
Returns: 3
"xzkvvkkkkkkbcxkkk"
4
Returns: 5
"oiidoooodooiakiooopddoiidaooiddppiopdddoodd"
7
Returns: 8
"vpvvvvvvvkvvvvvvvvppvvvppvkkvbvvkvpvvvvvv"
15
Returns: 0
"jjjjjjjjjjvojsjjjjojjjjjjjjjjjsjjjvjjjjjjjjjjjvjj"
15
Returns: 0
"ztvhhhgzhhhvvvlzhvvzrvzvhhv"
8
Returns: 2
"vveevwweev"
4
Returns: 0
"xaxwxxaxxxaxwawkxaxakxxxwxxxaaxwxxxaxwaxxxkaxwx"
6
Returns: 16
"wowwowwwwwwkwwwwwkwiwwwvkwwwwwwwwwkwywwwwvwwkwwwww"
15
Returns: 0
"ymmmmmmmyhmmymmhmm"
8
Returns: 0
"xtxxxxttxtxxxxxxtxxxttxttttxt"
12
Returns: 0
"sbhhfbsbbhfbhsbhbbfhbbhhh"
20
Returns: 0
"hhhhhhhnnhhhhhhhhhnnhhhhhhhhhhhhhhhhhhhhhhhhn"
20
Returns: 0
"eeeeeeeeeeeeezeeeeee"
18
Returns: 0
"kkkkkbtktkbkkkt"
10
Returns: 0
"klkkkllklqlkllllkkklkklklkkklllkkkkllkk"
20
Returns: 0
"sssessoooososssoos"
14
Returns: 0
"iikiiiawiiaaaaaatarttriiiaairaiaii"
20
Returns: 0
"kasuukqaqaukauauuaaqaaka"
14
Returns: 0
"fffffffffffffffffffffsffffsf"
15
Returns: 0
"dddddddddddddddd"
7
Returns: 0
"ggughghggggggggguhcggggggghgggggugghugghggg"
16
Returns: 0
"x"
0
Returns: 0
"jjujuujgjjjjjjjjuujuujjg"
19
Returns: 0
"ppppuuddduppppuudppppdppuupppupduuuuu"
3
Returns: 9
"nmrnwjnnnnnmmnnmn"
4
Returns: 5
"oooooooooooooooooooooooobooooooo"
4
Returns: 0
"kudddddkuhdhuuddduhkhuhdudddddhhdkd"
19
Returns: 0
"eeexeeeqexeeeeeexeeeeeeqeeeeeleexexeexl"
25
Returns: 0
"mmhhjmhhmhhjmmhmmmmhjmmjhhhmmhmhhhmmhmemjhmmmmmmm"
4
Returns: 18
"fuuuufufuuuuuhuufff"
12
Returns: 0
"rrrmmrrmrmrmmkmmgmmmkrmmmgrmmrmrmrmrm"
7
Returns: 4
"ytyyyyybbyybsyyysyyyycyysbyyybyyyyy"
29
Returns: 0
"uumvvevu"
5
Returns: 0
"krkrkkukkkururkruirutrukukukkuukukurukrum"
18
Returns: 0
"rewewwtewwewewenwrawewewtnwwee"
23
Returns: 0
"xxrcxfxkkxxxxxxxxfxx"
12
Returns: 0
"wfwfzfffffwffzwf"
6
Returns: 0
"ppgpiggpgppppppipsppppppppsgpgpgsppisppisgppgppp"
2
Returns: 24
"nskfknkffk"
6
Returns: 0
"wwwwwwwwwwwwrww"
1
Returns: 0
"bcbbcnbbbbcbcnbbbbbbbbcbbnccnbbbnbbcbbccbb"
30
Returns: 0
"ssqqslssouslsslssfssqolsssss"
6
Returns: 10
"ttccctbctsctccctcccccttccbccctcacccc"
10
Returns: 8
"nn"
1
Returns: 0
"gqgqqggpgggqgbgggqxggggggqqggpggxgbqqgbggg"
7
Returns: 17
"affffffffffffffffffffnfsffffffffffffffafffffff"
18
Returns: 0
"qjdjddjjjcdjdjddcjdddjdjjjdddjjejjjddjjdd"
5
Returns: 0
"iiiiiidiiiiiiikiiiiaii"
21
Returns: 0
"ioooooboobioioiiobbooo"
5
Returns: 4
"qqqqqqqqqqqqqqqqqq"
16
Returns: 0
"ijiijjjiiijijiiijijijiijijcijijiijjiijjijiiiii"
26
Returns: 0
"epeeeee"
4
Returns: 0
"cnnrynnnxcxnxrryvyyynnnrvxyvcxnynnbyn"
26
Returns: 0
"hhhhbhbhhhhvbhhhhhbhhhhhhhhhhhhhhhhhhh"
3
Returns: 27
"pppppkpeppperrpphppeppepppphpprppppppppppep"
38
Returns: 0
"xggggtg"
5
Returns: 0
"oooooodoooooooooooooooodoooooooooooooooodzoo"
16
Returns: 0
"ckhihccvhhheikhichkicheihhvxkhi"
28
Returns: 0
"azztzzzzzz"
6
Returns: 0
"sssxrsssrssrrrsrsrrrsrrssssxsssr"
23
Returns: 0
"jivwjvvj"
3
Returns: 0
"jqtotootttttoxttttjootjtttotoo"
5
Returns: 7
"brbxxlblsrxbmmx"
2
Returns: 2
"mbmmekmmmmsmmmmmzmkmmzkmmkmmzkmmm"
22
Returns: 0
"gnseqyedjtvkgrzoqcgnjufxbmtths"
1
Returns: 2
"mdyjfrwcwrhstqpwuygrtwoowubdnjgal"
28
Returns: 0
"pmicwbkicrogyoaifrybewtapsuwuhmejnj"
9
Returns: 0
"pamkxmjqamrnmiyqijozbvxlpceta"
23
Returns: 0
"bxfcbkxzvjqoxqvpdodpikavompygkpvbfojnttjvosts"
35
Returns: 0
"mccmgphlzvvgrtzjvxzewvoipobmyynkhwpeyxakw"
14
Returns: 1
"zaponsjkowvyiiezezrhsyqfpdeehmygwklxtdeurwphbsf"
7
Returns: 2
"eewhhngydvquolkkezgkfxrtbkqwuzeiklqlvdhqisoee"
38
Returns: 0
"cuewzkalxjjsuuanodfmzrphatavgnseqyedjtvkgrzoqcgnju"
7
Returns: 2
"rogyoaifrybewtapsuwuhmejnjoipamkxmjqamrnmiyqijozbv"
17
Returns: 1
"pcetaezvoghkhqjdfodfllxgeyfbdksxytovxrcazqrxucnxgi"
6
Returns: 2
"liciqbxfcbkxzvjqoxqvpdodpikavompygkpvbfojnttjvosts"
49
Returns: 0
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaz"
0
Returns: 48
"zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzabcdefgujikola"
14
Returns: 0
"qqwweerrttyyuuiiooppllkkjjhhggffddssaazzxxccvvbbnn"
49
Returns: 0
"bccdddeeeefffffgggggghhhhhhhiiiiiiiijjjjjjjjj"
43
Returns: 0
"aaaaaabbbbbbbbccccccccdddddeeeeefgggggghhhhhhhhh"
45
Returns: 0
"aaaabbbbcc"
2
Returns: 0
"aabbcccddddeeeeffffffff"
4
Returns: 2
"abbcabvabbvcabvbabdfabdhgbsd"
16
Returns: 0
"asdsadasdaaaaaaaaaaaaaaaaaaaaaa"
2
Returns: 20
"aaaaaabbbbbbcc"
3
Returns: 0
"zzzzzaaaaabbbbbbcccccccddddddddeeeeeeeeeffffffffff"
20
Returns: 0
"abcdefghijklmnopqrstuvwxxxssdeefdsssdfds"
29
Returns: 0
"aksdjfhaieuhaklsjefiuasdasdgfsdglfkjehfuiashlefiuh"
49
Returns: 0
"aaaaaabbbbbcccccddeeffgghhiijj"
7
Returns: 1
"asdaiuiuiouiiiiiididdididiididiiiiaaaakkksadsaddd"
40
Returns: 0
"aaaaaaabbbbbcccdd"
6
Returns: 1
"abcdzxmndjkjnlksndklsndlkjnsjdnsjbanban"
15
Returns: 0
"aabbc"
1
Returns: 0
"aaaaaaaaaabcdefghijkbcdefghijkbcdefghijkllllllllmm"
49
Returns: 0
"abcccdddd"
3
Returns: 0
"qqweerttyuuioopllkjjhggfddsaazxxcvvbnnm"
34
Returns: 0
"aaaabc"
2
Returns: 0
"abcccccdddddd"
2
Returns: 1
"gggggggooooooodddddddllllllluuuduuuuccckkk"
5
Returns: 4
"aaabbbcccxyz"
2
Returns: 2
"aaaaabb"
2
Returns: 0
"aaaassssddddee"
3
Returns: 0
"aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy"
20
Returns: 0
"aabbbcccdddeeefffggg"
2
Returns: 0
"abbbccccc"
2
Returns: 1
"aaabbcccddd"
3
Returns: 0
"aaabbbcccdefgh"
3
Returns: 1
"ghhghghgghghghg"
4
Returns: 0
"aaabbbbccccc"
3
Returns: 0
"cbbbadabdcbcbdcdcccbbcadcbddb"
5
Returns: 2
"abcdefghijklmnopqrstuvwxyzabcdefghijklmn"
39
Returns: 0
"ababababababababababababababababababababababababab"
0
Returns: 0
"cadaeafagahaiajakalamanaoapauaaaabbbbbbbbbbbbbbbbb"
15
Returns: 1
"aaaaabbbbbcccccddeeeeeefffggggghhhiiijjjkkkllmmmmm"
25
Returns: 0
"aaaaabbbbc"
1
Returns: 1
"abcfggddddddddddddeeeeeeeeeeee"
7
Returns: 0
"aaaabcbcbcddefe"
5
Returns: 0
"aabbbbbcccdddddd"
3
Returns: 2
"aaabbbcccdef"
3
Returns: 0
"bnwtvvahhxmympwgwke"
2
Returns: 1
"gggggggooooooodddddddllllllluuuuuuuccccckkkkk"
5
Returns: 1
"asfksd"
0
Returns: 1
"aabbbbcccccccc"
6
Returns: 0
"knakanenakokenanonekankanak"
6
Returns: 0
"aaaaabbbbbbbbbccccccccc"
4
Returns: 2
"aaaaaaaaaabbbbbbbbbbccccccccccrrrrrrrrrrttttttt"
4
Returns: 2
"aaaaaaaaaab"
1
Returns: 0
"jfdjgdhjghdjkhghisdhflsjfjhfreiemvriugdgjdf"
7
Returns: 4
"ggggggggkkc"
3
Returns: 0
"llkkppsssaaaaaaaaa"
6
Returns: 1
"aaabbbbbbcccccc"
3
Returns: 0
"abcdeeeeefffffggggg"
3
Returns: 3
"abbbccccddddd"
7
Returns: 0
"abcdefghzijklmnopqrstuvwxyzaaaddfdegagaffffadfaggg"
43
Returns: 0
"abbccddeee"
4
Returns: 0
"aaaaaaaabcdefghhhhhhaaaaaaaabcdefghhhhhhjkljklasdf"
49
Returns: 0
"abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx"
49
Returns: 0
"aaabbbbcccccdddddd"
3
Returns: 1
"aaaaabbbbbcccccdddddaaaaabbbbbcccccdddddaaaaabbbbb"
49
Returns: 0
"aaabbbcde"
3
Returns: 0
"aaaaaaaaaabbbbbbbbbbqwertyuiopqwezxd"
10
Returns: 4
"abcdefghijklmnopqryyyyyyzzzzzz"
4
Returns: 3
"aaaccceehkkllnnnppsuxxyyz"
5
Returns: 1
"aaaaaaaaaacccccccceeeeeeffffwwggggggggggggoooooooo"
49
Returns: 0
"abcdefghijklmnopqrstuvwxyzzzzzzzzzzzzzzzzzzzzzzzzz"
40
Returns: 0
"aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy"
49
Returns: 0
"aabbbccc"
1
Returns: 1
"dsaoiaehfoihdsljfhsladsaehrdrhasdnsfjkadsnf"
12
Returns: 2
"qqwweerrttyyuuiiooppaassddffgghhjkllzzxxccvvbbnnmm"
49
Returns: 0
"bbbbccccddeef"
3
Returns: 1
"aaaaaaaaaaaaagggbbccddeeff"
10
Returns: 1
"aaaaaaaaaa"
0
Returns: 0
"abbcccddddeeeeeffffffggggggghhhhhhhhttttttttt"
40
Returns: 0
"aaaaaaabbbbbbbccddee"
8
Returns: 0
"aaaabbbbbbbccccdddddddzzzzxxxxxxxxxxxxxxxxxx"
15
Returns: 2
"aaaaaaaaaabbcc"
4
Returns: 0
"aaaaabbbb"
1
Returns: 0
"kjhrewqrtascvqghewhjkytewlhuteqhiedcwqsbmnbfvrwerg"
49
Returns: 0
"aaaaaaaaaabbbbbbbbbbccccccccccddddddddddefgh"
4
Returns: 0
"aaaaabbbbbccccddeeffgghhjj"
10
Returns: 0
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
0
Returns: 0
"abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx"
45
Returns: 0
"aaabbbccccde"
3
Returns: 0
"aabbbbccccccdddddddd"
6
Returns: 1
"aaaaaaabbbbbbbccccddddeefgh"
5
Returns: 3
"abcdefghijklmnopqrstuvwxyabcdefghijklmnopqrstuvwxy"
49
Returns: 0
"aaaaaaabbbbbbbbccccccccc"
3
Returns: 0
"aaabbbbbbbccccccc"
3
Returns: 0
"aaaabbbaaccchhhhhfjkddddffjgjtttyrueqiijj"
20
Returns: 0
"aaaaaaabbbbbbcd"
2
Returns: 1
"aaaaaaaaaaaaaaaaaaaaaaaaabcdefghijklmnopqrstuvwxyz"
49
Returns: 0
"aaaaaaaabc"
2
Returns: 0
"abbbbbbbbbbccccccccccccccccccc"
2
Returns: 8
"qwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjkltyrfb"
49
Returns: 0
"aaaabbbbbbbbbbbccccccccccc"
3
Returns: 6
"aaaaaaaaaaaaaaaaaaaaaaaaannnnnnnnnnnnnnnnnnnnnnnnn"
49
Returns: 0
"aabbccddeeyyyyyyyyyyzzzzzzzzzz"
10
Returns: 0
"aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbcccccccccc"
49
Returns: 0
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
0
Returns: 48
"aaaaaaabbbbbbcccccddddeeefffgghhiijjklmnopr"
22
Returns: 1
"abcddeeffggghhhiiijjjjkkkkllllmmmmmnnnnnoooooppppp"
49
Returns: 0
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcdefghijk"
46
Returns: 0
"aaaaabbbbbcccccdddddeeeeeffffggghhyuiopm"
9
Returns: 2
"aaabbbcccdd"
2
Returns: 0
"dfgfgfdfgdfwerrdudfrtujyukjhhfvgjuhjkjyuuoiuoiuio"
23
Returns: 0