Remove All Adjacent Duplicates in String II
MedPrompt
You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.
We repeatedly make k duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.
Example 1:
Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.Example 2:
Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation:
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"Example 3:
Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"
Constraints:
1 <= s.length <= 1052 <= k <= 104sonly contains lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It repeatedly scans the string, and whenever it finds a sequence of k identical adjacent characters, it removes them. The process is repeated until a full scan of the string finds no such sequences. While straightforward to understand, this method is very inefficient because each removal may require re-scanning the entire string from the beginning.
Algorithm
- Convert the input string
sinto aStringBuilderfor efficient modifications. - Enter a loop that continues as long as removals are being made in a pass.
- Inside the loop, set a flag, say
foundDuplicates, tofalse. - Iterate through the
StringBuilderfrom left to right. - At each position, check if the next
kcharacters are identical. - If they are, delete that substring of length
kfrom theStringBuilder. - Set
foundDuplicatestotrueand break the inner loop to restart the scan from the beginning of the modified string. - If the inner loop completes without finding any duplicates to remove (
foundDuplicatesremainsfalse), exit the outer loop. - Return the final string from the
StringBuilder.
Walkthrough
We use a StringBuilder to allow for efficient character removal compared to immutable String objects. The main logic is wrapped in a while loop that continues as long as we can find and remove duplicates. In each iteration of this loop, we scan the string. If we find k adjacent, identical characters, we remove them and restart the scan. If we complete a full scan without any removals, the string is in its final state, and we can terminate.
class Solution { public String removeDuplicates(String s, int k) { StringBuilder sb = new StringBuilder(s); boolean changedInPass = true; while (changedInPass) { changedInPass = false; for (int i = 0; i + k <= sb.length(); i++) { char currentChar = sb.charAt(i); boolean allSame = true; for (int j = 1; j < k; j++) { if (sb.charAt(i + j) != currentChar) { allSame = false; break; } } if (allSame) { sb.delete(i, i + k); changedInPass = true; // A removal might create a new duplicate group at the join point, // so we must restart the scan. break; } } } return sb.toString(); }}Complexity
Time
O(N^2 / k). In the worst-case scenario, we might perform O(N/k) removal operations. Each removal and subsequent scan costs O(N), leading to a quadratic time complexity. For a small `k`, this approaches O(N^2).
Space
O(N), where N is the length of the string. This space is used to hold the `StringBuilder`.
Trade-offs
Pros
Simple to conceptualize and implement.
Cons
Highly inefficient due to repeated scanning of the string.
String/StringBuilder deletion is an O(N) operation, leading to poor overall performance.
Will result in a 'Time Limit Exceeded' error on large inputs.
Solutions
Solution
class Solution {public String removeDuplicates(String s, int k) { Deque<int[]> stk = new ArrayDeque<>(); for (int i = 0; i < s.length(); ++i) { int j = s.charAt(i) - 'a'; if (!stk.isEmpty() && stk.peek()[0] == j) { stk.peek()[1] = (stk.peek()[1] + 1) % k; if (stk.peek()[1] == 0) { stk.pop(); } } else { stk.push(new int[]{j, 1}); } } StringBuilder ans = new StringBuilder(); for (var e : stk) { char c = (char)(e[0] + 'a'); for (int i = 0; i < e[1]; ++i) { ans.append(c); } } ans.reverse(); return ans.toString(); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.