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
Water Flow | InterviewBit | Solution Explained
May 11, 2022