Sherlock and the Valid String

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:

all the characters occur the same number of times: the solution is “YES”;
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);
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);
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
- 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<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";
}

This Rust solution does not use an additional structure:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


fn is_valid(s: &str) -> &'static str {
    let mut freqs: [usize; 26] = [0; 26];

    for x in s.as_bytes() {
        let y = (x - b'a') as usize;
        freqs[y] += 1;
    }

    let max_freq = *freqs.iter().max().unwrap();
    let min_freq = *freqs.iter().filter(|&&x| x > 0).min().unwrap();
    let min_freq_not_one = freqs.iter().filter(|&&x| x > 1).min().copied();
    let max_freq_count = freqs.iter().filter(|&&x| x == max_freq).count();
    let min_freq_count = freqs.iter().filter(|&&x| x == min_freq).count();

    let valid =
        // all the characters occur the same number of times
        (min_freq == max_freq) ||
        // all the characters occur the same number of times except for one which occurs only once
        (min_freq == 1 && min_freq_count == 1 && (Some(max_freq) == min_freq_not_one)) ||
        // all the characters occur the same number of times except for one which occurs once more the others
        ((max_freq - min_freq) == 1) && (max_freq_count == 1);

    if valid { "YES" } else { "NO" }
}

frequency table