Hard: Sherlock and valid string
March 7, 2023
Question: Given a string, Sherlock considers it valid if all the characters in the string occur the same number of time. However, a string is also valid if the frequencies are same after removing any one character.
Example 1:
Input: str = “aabbcd”
Output: NOExample 2:
Input: str = “abcc”
Output: YES
Problem statement
Let's break down the problem statement (opens in a new tab).
Sherlock needs to verify if a given string is valid. A string is valid under 2 conditions:
- All characters of the string have same frequencies
- If you can delete any one character from the string to achieve condition #1.
Solution
- Init map then find out how many repetition of char
- Return
YES
if string input consist of 1 char only such as "aaaa" or "bbb" or "zz" - Init another map to find out how many char with
X
frequency - Find the most frequencies occurred
- Iterate from the first map
kind
- Check if the current frequency is different with
mainFreq
- Return
NO
ifhasUniqFreq
or different frequency more than 1, otherwise sethasUniqFreq
true - Return
YES
Try it yourself https://go.dev/play/p/jtD3sCn5LkJ (opens in a new tab)