# Sherlock and the Valid String

See the original problem on HackerRank.

## Solutions

Warning: HackerRank does not fully cover this challenge with tests. You can write a solution which passes all the tests but not this test case:

 1  aaavvbbb 

That should be NO.

An example of code that passes all the tests but the one above:

 1 2 3 4 5 6  fun isValid(s: String): String { val listLetters = s.groupingBy { it }.eachCount().toList() val dif = listLetters.filter { listLetters.first().second != it.second }.size return if (dif <= 1) "YES" else "NO" } 

Our solutions work as we expect.

We have four main cases:

1. all the characters occur the same number of times: the solution is “YES”;
2. all the characters occur the same number of times except for one which occurs only once: the solution is “YES” (since such a character can be removed);
3. all the characters occur the same number of times except for one which occurs once more the others: the solution is “YES” (since such a character can be removed);
4. otherwise, the solution is “NO”.

Thus, we need to group the characters by frequency. We can use different strategies, such as frequency table and set (to count how many frequencies we have), or Python’s Counter.

Here is a C++ solution:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31  string isValid(const string& s) { array freq{}; for (auto c : s) freq[c-'a']++; set uniques; copy_if( begin(freq), end(freq), inserter(uniques, end(uniques)), [](auto i) { return i>0; }); // all have the same frequency if (uniques.size() == 1) return "YES"; // more than 2 trends if (uniques.size() > 2) return "NO"; // at this point, we know there are only two "groups" auto minTrend = *begin(uniques); auto maxTrend = *next(begin(uniques)); // only one character occurs once if (minTrend == 1 && count(begin(freq), end(freq), minTrend) == 1) return "YES"; // difference between the groups is 1 and only one character has such a frequency return (maxTrend - minTrend == 1 && count(begin(freq), end(freq), maxTrend) == 1) ? "YES" : "NO"; } 

Here is a solution in Python:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28  from collections import Counter def check(cnt): ls = cnt.values() try: ls.remove(0) except: pass if len(set(ls)) == 1: return True else: return False def isValid(s): cnt = Counter(s) if check(cnt): return "YES" for i in cnt.keys(): cnt[i] -= 1 if check(cnt): return "YES" else: cnt[i] += 1 return "NO" s = raw_input().strip() result = isValid(s) print(result) 

A variation, left as exercise, consists in not using any additional data structure (e.g. set): we know that only two “groups” may exist, we can just scan the frequency table to search for those. If we find more than 2, we fail. The rest of the algorithm is the same.

Just for fun, another very simple solution consists in a brute force approach. Since the domain is limited, this solution is - surprisingly for someone - still linear in time.

Here is the idea:

• fill the frequency table
• remove zeros
• check if all the elements are the same
• if so, it’s “YES”
• otherwise, for each frequency:
• subtract one from the current frequency
• do the check again (ignore possible new zero)
• if all the frequencies are equal, it’s “YES”
• restore the old frequency (add 1)
• if here, it’s “NO”

Two implementations in C++ to show you some STL patterns:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  string isValid(const string& s) { vector freq(26); for (auto c : s) freq[c-'a']++; freq.erase(remove_if(begin(freq), end(freq),[](auto i){ return i==0; }), end(freq)); if (std::adjacent_find(begin(freq), end(freq), not_equal_to<>()) == end(freq)) return "YES"; for (auto &i : freq) { i -= 1; if (all_of(begin(freq), end(freq), [&](auto j) { return j == 0 || j == freq.front(); })) return "YES"; i += 1; } return "NO"; } 

In the following one, we do not remove zeros first because we do some special handling in all_of:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  string isValid(const string& s) { vector freq(26); for (auto c : s) freq[c-'a']++; if (all_of(begin(freq), end(freq), [&](auto j) { return j == 0 || j == freq.front(); })) return "YES"; for (auto &i : freq) { i -= 1; if (all_of(begin(freq), end(freq), [&](auto j) { return j == 0 || j == freq.front(); })) return "YES"; i += 1; } return "NO"; } 
We've worked on this challenge in these gyms: modena