Teaching Kids Programming – Using GroupBy Algorithm to Compress String

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string lowercase alphabet s, eliminate consecutive duplicate characters from the string and return it. That is, if a list contains repeated characters, they should be replaced with a single copy of the character. The order of the elements should not be changed.

Constraints
0 ≤ n ≤ 100,000 where n is the length of s
Example 1
Input
s = “aaaaaabbbccccaaaaddf”
Output
“abcadf”
Example 2
Input
s = “a”
Output
“a”

Try maintaining 2 pointers to remove the duplicates in place.

Using GroupBy Algorithm to Compress a String

Let’s remember the previous character and if current character diffs, we need to push it to the array and lastly we join the array to string. The reason of using array/list and then converting to string is that the direct string concatenation is slower than appending an element into the array.

1
2
3
4
5
6
7
8
9

class Solution:
    def solve(self, s):
        ans = []
        prev = None
        for i in s:
            if not prev or prev != i:
                ans.append(i)
            prev = i
        return "".join(ans)

class Solution:
    def solve(self, s):
        ans = []
        prev = None
        for i in s:
            if not prev or prev != i:
                ans.append(i)
            prev = i
        return "".join(ans)

We can iterate over the indices and compare the characters at current index and its previous one.

1
2
3
4
5
6
7

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

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

In Python, we have groupby function from itertools so that we can use list comprehension to return the group directly.

1
2
3

class Solution:
    def solve(self, s):
        return "".join([x for x,y in groupby(s)])

class Solution:
    def solve(self, s):
        return "".join([x for x,y in groupby(s)])

All time complexity is O(N) where N is the number of characters in the list.

See also: Runlength Compression Algorithm, Demonstration in Python

–EOF (The Ultimate Computing & Technology Blog) —