HackerRank ‘Sherlock and Valid String’ Solution

H
Short Problem Definition:

Sherlock considers a string to be valid if all characters of the string appear the same number of times. It is also valid if he can remove just 1 character at 1 index in the string, and the remaining characters will occur the same number of times. Given a string , determine if it is valid. If so, return YES, otherwise return NO.

Link

Sherlock and Valid String

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

I optimized 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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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"

About the author

Add comment

Archives

Categories