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.
time complexity is O(N)
space complexity is O(1)
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.
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.