Teaching Kids Programming – Remove Consecutive Duplicates

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string s, consisting of “X” and “Y”s, delete the minimum number of characters such that there’s no consecutive “X” and no consecutive “Y”.

Constraints
n ≤ 100,000 where n is the length of s
Example 1
Input
s = “YYYXYXX”
Output
“YXYX”
Explanation
One solution is to delete the first two “Y”s and the last “X”.

Hints:
Each consecutive block can considerated as 1 unit.
Think for two pointer approach.

String Algorithm to Remove Consecutive Duplicates

There are only two characters: “X” and “Y”, therefore we can repeatedly replace “XX” with “X” and “YY” and “Y” to remove the Consecutive same characters:

1
2
3
4
5
6
7

class Solution:
    def removeConsecutiveDuplicates(self, s):
        while "XX" in s:
            s = s.replace("XX", "X")
        while "YY" in s:
            s = s.replace("YY", "Y")
        return s

class Solution:
    def removeConsecutiveDuplicates(self, s):
        while "XX" in s:
            s = s.replace("XX", "X")
        while "YY" in s:
            s = s.replace("YY", "Y")
        return s

Time complexity O(N^2) due to checking substring existence O(N) and we replace it to get a new string.

A better approach is to go through each character and then check if it should be included. If the current character is the same as the previous included character, we skip, otherwise we keep.

1
2
3
4
5
6
7

class Solution:
    def removeConsecutiveDuplicates(self, s):
        ans = []
        for c in s:
            if len(ans) == 0 or c != ans[-1]:
                ans.append(c)
        return "".join(ans)

class Solution:
    def removeConsecutiveDuplicates(self, s):
        ans = []
        for c in s:
            if len(ans) == 0 or c != ans[-1]:
                ans.append(c)
        return "".join(ans)

Time complexity is O(N) and the space complexity is O(N) due to that we store the results in a list.

We can also use the itertools.groupby to do this easily:

1
2
3

class Solution:
    def removeConsecutiveDuplicates(self, s):
        return "".join([x for x, _ in itertools.groupby(s)])

class Solution:
    def removeConsecutiveDuplicates(self, s):
        return "".join([x for x, _ in itertools.groupby(s)])

–EOF (The Ultimate Computing & Technology Blog) —