How would you remove duplicates in a string?
Medium
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.
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). For the final reconstruction, although each char * count operation may repeat a character multiple times, the total number of characters across all stack elements is bounded by n (since no character is added to the stack more than once per original character in s). Hence the join is O(n), and the overall time complexity is O(n).
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.
Interview experiences
2 sharedRelated questions
How would you implement retries without causing duplicate operations?Remove duplicates in an array of objects.How would you improve Rover?Related courses
