Stack and queue - 1047. Delete all adjacent duplicates in the string

1 Title Description

Give a string of lowercase letters S, Duplicate deletion selects two adjacent and identical letters , And delete them .

stay S Repeat the delete operation on , Until you can't delete .

Returns the final string... After all the duplicates have been deleted . The answer is guaranteed to be unique .

2 Title Example

Input ：“abbaca”
Output ：“ca”
explain ：
for example , stay “abbaca” in , We can delete “bb” Because two letters are adjacent and the same , This is the only duplicate that can be deleted at this time . And then we get the string “aaca”, There is only “aa” You can perform a duplicate deletion operation , So the last string is “ca”.

3 Topic tips

1 <= S.length <= 20000
S It's only made up of lowercase letters .

4 Ideas

After fully understanding the meaning of the question , We can find out , When there are multiple groups of adjacent duplicates in a string at the same time , No matter which one we delete first , Will not affect the final result . So we can process the string in turn from left to right .
And eliminate — For adjacent duplicates, new adjacent duplicates may appear , Such as from string abba Delete in bb Will result in new adjacent duplicates aa appear . So we need to save the characters that haven't been deleted yet . An obvious data structure is just around the corner : Stack . We just need to traverse the string , If the current character is the same as the top of the stack , We greedily eliminate it , Otherwise, put it on the stack .
Complexity analysis
· Time complexity :O(n), among n Is the length of the string . We only need to traverse the string once .
Spatial complexity :O(n) or o(1), It depends on whether the string class provided by the language used provides a similar 「 Push 」 and 「 Out of the stack 」 The interface of . Note that the return value is not included in the spatial complexity .

5 My answer

class Solution {
    
    public String removeDuplicates(String s) {
    
        StringBuffer stack = new StringBuffer();
        int top = -1;
        for (int i = 0; i < s.length(); ++i) {
    
            char ch = s.charAt(i);
            if (top >= 0 && stack.charAt(top) == ch) {
    
                stack.deleteCharAt(top);
                --top;
            } else {
    
                stack.append(ch);
                ++top;
            }
        }
        return stack.toString();
    }
}