Remove Duplicates in String
Remove Adjacent Duplicates in String. You are given a string s and an integer k. Write a function to remove k adjacent duplicates from s where the "adjacent" characters are equal.
For instance, if k is 3 and the string is "daaabbbaa", since we have "aaa" and "bbb" as adjacent triples, the function should transform the string to "daa", removing the "bbb" first and then the remaining "aaa".
Examples
s = 'abcd' k = 2 output: 'abcd' s = 'deeedbbcccbdaa' k = 3 output: 'aa' s = 'pbbcggttciiippooaais' k = 2 output: 'ps' s = 'aaabbbacd' k = 3 output: 'acd'
In each example, output refers to the resulting string after all possible k adjacent duplicates have been removed.
The function identifyAdjacent removes adjacent duplicate characters from a string s if they appear k times consecutively. The approach uses a stack to keep track of characters and their counts, ensuring efficient removal of duplicates.
-
Initialize the Stack: We use a stack to store pairs of characters and their consecutive counts. Each element in the stack is a
[char, count]pair that can be implemented using a list, tuple or custom data structure. -
Iterate Over the String: For each character
charin the strings:
- If the stack is not empty and the top element of the stack has the same character as
char, increment the count of the top element. - If the stack is empty or the top element has a different character, push a new
[char, 1]element onto the stack. - If the count of the top element reaches
k, pop it from the stack to remove the adjacent duplicates.
- Construct the Result String: After processing all characters, reconstruct the string from the stack by repeating each character according to its count.
def identify_adjacent(s, k):
stack = [] # Initialize an empty stack to store <char, count> pairs
for char in s:
if stack and stack[-1][0] == char:
stack[-1][1] += 1 # Increment the count of the top element if it's the same character
else:
stack.append([char, 1]) # Push a new character with count 1 onto the stack
if stack[-1][1] == k:
stack.pop() # Remove the top element if its count reaches k
# Reconstruct the result string from the stack
return ''.join(char * count for char, count in stack)Time Complexity O(n). We traverse the string s of length n once. Each push and pop operation on the stack takes constant time O(1). Hence, the overall time complexity is linear with respect to the length of the input string.
Space Complexity: O(n). In the worst case, all characters in the string are unique or do not reach the count k to be removed, resulting in storing all characters in the stack. Thus, the space complexity is linear with respect to the length of the input string.
How would you update an input string to remove repeated characters and concatenate the result into a combined string? Watch Ravi, FAANG software engineer, answer this mock interview question.
# O(n) - characters in the string # O(n) - stack def identify_adjacent(s: str, k: int) -> str: stack = [] n = len(s) for ch in s: if stack: top_ch, top_cnt = stack[-1] if top_ch == ch: top_cnt += 1 stack[-1] = (ch, top_cnt) else: top_cnt = 1 stack.append((ch,1)) if top_cnt == k: stack.pop() else: stack.append((ch,1)) return "".join([ch * count for ch, count in stack]) # debug your code below print(identify_adjacent("abcd", 2))