Remove All Adjacent Duplicates In String
EasyPrompt
You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.
Example 1:
Input: s = "abbaca"
Output: "ca"
Explanation:
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".Example 2:
Input: s = "azxxzy"
Output: "ay"
Constraints:
1 <= s.length <= 105sconsists of 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, finds the first pair of adjacent duplicates, removes them, and then starts the scan over from the beginning of the new, shorter string. This continues until a full pass over the string reveals no adjacent duplicates.
Algorithm
- Start with the input string
s. - Enter a loop that continues as long as modifications are being made to the string.
- In each iteration of the loop, find the index
iof the first occurrence wheres[i] == s[i+1]. - If such a pair is found, create a new string by removing the characters at indices
iandi+1. Updatesto this new string and restart the scan from the beginning. - If a full scan of the string is completed and no adjacent duplicates are found, exit the loop.
- The final string
sis the result.
Walkthrough
This method uses a loop that continues as long as it can find and remove a pair of adjacent, identical characters. Inside the loop, it iterates through the string to find the first such pair. Upon finding one, it removes the pair, effectively shortening the string, and then breaks the inner loop to restart the scan from the beginning of the modified string. This process is guaranteed to terminate because the string's length decreases with each successful removal. While simple to conceptualize, the repeated creation of new string objects (or manipulation of a StringBuilder from the start) makes it very slow.
class Solution { public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(s); boolean found = true; while (found) { found = false; for (int i = 0; i < sb.length() - 1; i++) { if (sb.charAt(i) == sb.charAt(i + 1)) { sb.delete(i, i + 2); found = true; break; // Restart scan from the beginning } } } return sb.toString(); }}Complexity
Time
O(N^2), where N is the length of the string. In the worst-case scenario (e.g., 'abccba'), each removal operation can take O(N) time due to scanning and string/StringBuilder modification. Since there can be up to N/2 removal operations, the total time complexity is quadratic.
Space
O(N). In Java, a `StringBuilder` is used to make the string mutable, which requires O(N) space. If using immutable strings, each modification would create a new string, also leading to O(N) space usage for the intermediate strings.
Trade-offs
Pros
The logic is straightforward and directly follows the problem statement.
Cons
Extremely inefficient due to repeated scanning and string manipulations.
Likely to fail on larger test cases due to exceeding the time limit.
Solutions
Solution
class Solution {public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(); for (char c : s.toCharArray()) { if (sb.length() > 0 && sb.charAt(sb.length() - 1) == c) { sb.deleteCharAt(sb.length() - 1); } else { sb.append(c); } } return sb.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.