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 ina
. Both are of len = N. - Space:
O(N)
to store the consecutive characters string.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Please write the proof.
This solution need an amendment for 2 digit number.
Please write a Proof for this