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 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.