Given a string
s, recursively remove any adjacent duplicate characters that it contains.
s = "cooodefightssforrrcodee", the output should be
removeDuplicateAdjacent(s) = "cdefightfocod".
s = "acaaabbbacdddd", the output should be
removeDuplicateAdjacent(s) = "acac".
- [time limit] 4000ms (py)
- [input] string s
A string composed of lowercase English letters.
1 ≤ s.length ≤ 50.
- [output] string
A string obtained by removing all adjacent duplicates from the input string.
The problem ask us to remove duplicate characters. The important thing is, we need to consider the cases “abbac” that goes to “c”. So, just removing “bb” does not do the job. We need to iterate over it again and remove the adjacents in the remaining string, too.
First two variables are iteration counter variables (i and m). m starts from 1 and i starts from m. Every step, we check if the i-th element is equal to m-th element and if so, increase i. This loop will count all the consecutive same elements. Then, we can remove these elements from the string. We check if m and i are different. If they are not, this means the first element is not the same with any following character. Then, we don’t remove. We do this for all the elements in string. and remove all consecutive elements.
This takes us from “abbac” to “aac”, now, we recursively call this function again with “aac” to remove duplicates in this string. Note that these two loops does not change if the string does not have any duplicates but we call it recursively anyway, causing an infinite loop. Therefore, we need a flag variable “f” that we set to True when we change something in the string. If we don’t change anything, then it can return the string s.
Also, in line 16, we are decrementing m. It’s because if we are removing a letter from the string, our next character shifts to the index m. So, if we increase m here, we skip one letter. To take that into account, we need to keep m at the same place, so we decrease it by one here and in the next line we increase it by one, it stays the same.