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:
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<int, 'z''a'+1> freq{};
for (auto c : s)
freq[c'a']++;
set<int> 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
 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<int> 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<int> 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";
}
