HackerRank ‘Sherlock and Valid String’ Solution

Short Problem Definition:

A “valid” string is a string S such that for all distinct characters in S each such character occurs the same number of times in S.

Link

Sherlock and Valid String

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

I optimised this solution to the minimal case that passes all tests on HackerRank. It seems that each character occurs 1 or 2 times. I did not pay the Hackos to verify the input :). The logic of the solution is as follows: count the character counts for each character.

  • if they are all equal – it means that all characters occur exactly N times and there is no removal needed
  • if 2 or more have less or more characters – there is no way to fix the string in just 1 removal
  • if exactly 1 char has a different count than all other characters – remove this char completely and S is fixed.
Solution:
from collections import Counter


def isValid(S):
    char_map = Counter(S)
    char_occurence_map = Counter(char_map.values())

    if len(char_occurence_map) == 1:
        return True

    if len(char_occurence_map) == 2:
        for v in char_occurence_map.values():
            if v == 1:
                return True

    return False


S = raw_input()
if isValid(S):
    print "YES"
else:
    print "NO"

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Sidharth Samant

    Hi Martin. This code still passes all the test cases, but the provided test cases on HackeRank don’t cover all the possibilities, so I went ahead and implemented a few modifications in the function to cover them all (that is, if you are interested) –

    c = Counter(s)
    d = Counter(c.values())
    distinct_counts = list(set(d.elements()))

    if len(d) == 1:
    print “YES”
    elif len(d) == 2:
    the_greater_count = max(distinct_counts[0], distinct_counts[1])
    the_lesser_count = min(distinct_counts[0], distinct_counts[1])
    if the_greater_count – the_lesser_count == 1:
    if d[the_greater_count] == 1:
    return “YES”
    elif d[the_lesser_count] == 1:
    return “YES”
    return “NO”
    elif d[the_lesser_count] == 1:
    return “YES”
    return “NO”
    return “NO”

  • Sidharth Samant

    Hi Martin. I know you’ve stated you’ve covered only the minimal cases, and the code still works on HackerRank but I thought to go ahead and cover all the bases. So I modified the code to cover all the possibilites (I think) – https://gist.github.com/SidSam/6431ee029f38d7aca1ec90b7ec0e869f.
    Feel free to point out any mistakes I might have done. (or for that matter, any pointers on how to make my code more readable and “pythonic”)

    • Try this input “aabbbccc” 😉

      • Sidharth Samant

        Ah yes, that doesn’t work. Sigh…. I was so glad that I’d finally done something on my own. I’ve just started taking my programming career seriously, you see. Guess I should just keep on practicing.