Remove All Adjacent Duplicates
Given a string, remove all adjacent duplicates. For example, if the input string is "aabbc", the output should be "c" because all adjacent duplicates are removed.
Constraints:
- The input string only contains lowercase letters.
- The input string is not empty.
Examples:
Input: "aabbc"
Output: "c"
Explanation: The adjacent duplicates "aa" and "bb" are removed, leaving only "c".
Input: "abcd"
Output: "abcd"
Explanation: There are no adjacent duplicates, so the string remains the same.
Solutions
Stack-based Approach
We use a stack to keep track of the characters. We iterate through the string, and for each character, we check if the stack is empty or the top of the stack is not equal to the current character. If it's not equal, we push the character onto the stack. If it is equal, we pop the top character from the stack. Finally, we return the string representation of the stack, which is the input string with all adjacent duplicates removed.
public String removeDuplicates(String s) {
StringBuilder stack = new StringBuilder();
for (char c : s.toCharArray()) {
if (stack.length() == 0 || stack.charAt(stack.length() - 1) != c) {
stack.append(c);
}
else {
stack.deleteCharAt(stack.length() - 1);
}
}
return stack.toString();
}Follow-up:
How would you modify the solution to remove all duplicates, not just adjacent duplicates?
