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
- s = “aabcd”, k = 2 → “bcd”
- s = “aabbcccd”, k = 2 → “cd”
1. Remove Consecutive Characters: Observations & Logic
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
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*final_len return ns
2.1. Complexity Analysis
Where N = len(s)
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.
O(N)to store the consecutive characters string.
June 13, 2022
June 13, 2022