How to solve ‘removeDuplicateAdjacents’ in CodeFights

The Problem

Given a string s, recursively remove any adjacent duplicate characters that it contains.

Example

  • For s = "cooodefightssforrrcodee", the output should be
    removeDuplicateAdjacent(s) = "cdefightfocod".
  • For s = "acaaabbbacdddd", the output should be
    removeDuplicateAdjacent(s) = "acac".

Input/Output

  • [time limit] 4000ms (py)
  • [input] string s

    A string composed of lowercase English letters.

    Constraints:

    1 ≤ s.length ≤ 50.

  • [output] string

    A string obtained by removing all adjacent duplicates from the input string.

The Solution

asddasdasdas8.png

The Explanation

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.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s