This content originally appeared on DEV Community and was authored by quoc187
This is just me, blame myself and summarize my problem.
The problem here
According to the description, a valid string is a string that has all characters appears a CONST time(i will call it the perfect string), or just one character has more than 1 time appears.
But i misunderstood it, i thought we can remove one character(incase string is not perfect), and then it can possibly valid if we remove one more, and so on. It blows my brain, especially in the context of an interview, i get nervous, and then things go wrong.
The solution is very simple, the only thing we should care about is the frequencies, or in fact how many frequencies of character occurs in the string.
Step 1: create a mapping between character and its frequency
Step 2: create a mapping between the frequency and number of times it occurs
Step 3:
- Case 1: If there's more than 2 frequencies, it mean the string is not valid, no way to make a one frequency from removing a character
- Case2: If there's just 1 frequencies, the string is just one character repeat serveral times
- Case 3: Now the last case is 2 frequencies case, let say
aandb. We must delete one charater to make the string valid, but after deleting,aandb's value in the frequency map will be changed, to make a string valid, the final frequency map must contains just 1 key(case 2). First we must check ifaandboccurs 1 time, if both of them occurs more than 1 time, we can't make a string valid even after deleting one character.
Let say we wanna delete the character that has frequency of a, after deleting, we have a new frequency that is a-1, and the value of a in the frequency mapw will be reduced by 1
so we have a new frequency map { b: bOccurrences, a: aOccurences-1, [a-1]: 1 }
To make string valid, aOccurrences - 1 must be 0 and [a-1] must be b or 0, or in another words: aOcurrences == 1 and (a-1 ==b || a == 1) (note that obviously b cannot be 0)
Same approach with b.
If you feel confused, see the code below
Here is final solution in python
This content originally appeared on DEV Community and was authored by quoc187
quoc187 | Sciencx (2022-02-21T13:36:29+00:00) I failed an easy test. Retrieved from https://www.scien.cx/2022/02/21/i-failed-an-easy-test/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.