DEV Community

quoc187
quoc187

Posted on

I failed an easy test

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 1
Step 2: create a mapping between the frequency and number of times it occurs
Step2
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 Case 1
  • Case2: If there's just 1 frequencies, the string is just one character repeat serveral times Case 2
  • Case 3: Now the last case is 2 frequencies case, let say a and b. We must delete one charater to make the string valid, but after deleting, a and b'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 if a and b occurs 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
Image description

Here is final solution in python
Final

Top comments (0)