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