sherlock_valid_string.py

# source: https://www.hackerrank.com/challenges/sherlock-and-valid-string/problem
# video: https://youtu.be/WTwih7Ghvig
def isValid(s):
    count_of_chars = dict()
    
    for char in s:
        if char not in count_of_chars:
            count_of_chars[char] = 0
        count_of_chars[char] += 1
            
    count_of_counts = dict()
    for count in count_of_chars.values():
        if count not in count_of_counts:
            count_of_counts[count] = 0
            # too many unique counts means not possible
            # to remove just 1 char to make valid
            if len(count_of_counts) > 2:
                return 'NO'
        count_of_counts[count] += 1
    if len(count_of_counts) == 1: # all chars have same count!
        return "YES"
    # 2 unique count_of_counts at this point
    count_keys = list(count_of_counts.keys())
    first = min(count_keys)
    second = max(count_keys)
    if first == 1 and count_of_counts[first] == 1: # can just remove the one char
        return 'YES'
    if len(['blah' for val in count_of_counts.values() if val == 1]) != 1:
        # 2 count_of_counts both show up more than once => not valid
        return 'NO'
    if second - first == 1: # char shows up one more than other
        return 'YES'
    return 'NO' # Time Complexity: O(n) + O(n) = O(2n) => O(n)

I've added a correction on line 32 to ensure both the difference between counts is 1 AND the count of counts for the larger number is also 1.
This is because we can only remove a character, not add one.

I've updated my solution to coverage an untested case "abb", which should return "YES", but was instead returning "NO". The order of the logic was suboptimal, but was still passing all test on HackerRank (as of this writing). I've requested the author add this test case.