# HackerRank 'Sherlock and Valid String' Solution

Martin Kysel · February 23, 2016

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

Sherlock and Valid String

##### Complexity:

time complexity is `O(N)`

space complexity is `O(1)`

##### Execution:

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.

EDIT 2020: HR added some extra test cases and the solution no longer worked. I updated it to pass all the cases including a secret “aabbbccc” case that HR is not testing for.

##### Solution:
``````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:
k1, k2 = char_occurence_map.keys()
v1, v2 = char_occurence_map.values()

# there is exactly 1 extra symbol and it can be deleted
if (k1 == 1 and v1 == 1) or (k2 == 1 and v2 == 1):
return True

# the is exactly 1 symbol that occurs an extra 1 time
if (k1 == k2+1 and v1 == 1) or (k2 == k1+1 and v2 == 1):
return True

return False
``````