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:

 Remove Consecutive Characters: test case for string "aaabaaccc"
Remove Consecutive Characters: test case for string “aaabaaccc”

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?

 Remove Consecutive Characters: test case for k = 2
Remove Consecutive Characters: test case for k = 2

What if k = 3?

Remove Consecutive Characters: test case for k = 3
Remove Consecutive Characters: test case for 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.
Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.