Remove Consecutive Characters | InterviewBit | Solution Explained

InterviewBit Remove Consecutive Characters. Solution explained simply & in detail. Problem Link

0. Remove Consecutive Characters: Problem Discussion

0.0. IO Format

• Given: String s and integer k
• Goal: Return another string ns
• Condition: remove all k consecutive characters in s

0.1. Examples

• s = “aabcd”, k = 2 → “bcd”
• s = “aabbcccd”, k = 2 → “cd”

1. Remove Consecutive Characters: Observations & Logic

1.0. Intuitions

How do we start to think about this problem? Since the question mentions “consecutive characters”, we can start with that.

1.1. Consecutive Characters

The first goal is to identify and extract all the consecutive character sequences.

Since there could be many, we can store them in a list. This is how it looks:

1.2. Removing Consecutive Characters

Now we have to remove a sequence of k consecutive characters. Let’s say that k = 2 in our case. What will happen?

What if k = 3?

By now, we realize that the answer is simply taking the len(consecutive_characters) % k as the final length!

2. Remove Consecutive Characters: Optimized Implementation

2.0. Code

class Solution:
    def solve(self, s, k):
        i = 0
        a = []
        while i < len(s):
            a.append(s[i])
            while i+1 < len(s) and s[i] == s[i+1]:
                a[-1] += s[i]
                i += 1
            i += 1

        ns = ""
        for ccs in a:
            final_len = len(ccs)%k
            ns += ccs[0]*final_len
        
        return ns

2.1. Complexity Analysis

Where N = len(s)

• Time: O(N) to iterate over all the characters in s once and then to iterate over all the strings in a. Both are of len = N.
• Space: O(N) to store the consecutive characters string.