Remove All Adjacent Duplicates in String II | LeetCode | Java

Intuition: It uses a stack of custom objects Node to keep track of characters and their counts.

Algorithm:

1. It iterates through the characters of the input string s and checks if the current character matches the top character on the stack.
2. If it does, and the count of consecutive occurrences reaches k, the characters are removed from the stack. If not, a new Node is pushed onto the stack with count 1.
3. After processing the entire input string, the method constructs the resulting string by popping characters and counts from the stack and appending the characters the required number of times to a StringBuilder.
4. The final result is the reversed version of the StringBuilder, which is returned as the output.

<span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>String</span> <span>removeDuplicates</span><span>(</span><span>String</span> <span>s</span><span>,</span> <span>int</span> <span>k</span><span>)</span> <span>{</span>
        <span>Stack</span><span><</span><span>Node</span><span>></span> <span>stack</span> <span>=</span> <span>new</span> <span>Stack</span><span><>();</span>
        <span>for</span><span>(</span><span>char</span> <span>c</span> <span>:</span> <span>s</span><span>.</span><span>toCharArray</span><span>()){</span>
            <span>if</span><span>(!</span><span>stack</span><span>.</span><span>isEmpty</span><span>()</span> <span>&&</span> <span>stack</span><span>.</span><span>peek</span><span>().</span><span>ch</span><span>==</span><span>c</span><span>){</span>
                <span>if</span><span>(++</span><span>stack</span><span>.</span><span>peek</span><span>().</span><span>count</span><span>==</span><span>k</span><span>)</span>
                    <span>stack</span><span>.</span><span>pop</span><span>();</span>
            <span>}</span>
            <span>else</span><span>{</span>
                <span>stack</span><span>.</span><span>push</span><span>(</span><span>new</span> <span>Node</span><span>(</span><span>c</span><span>,</span> <span>1</span><span>));</span>
            <span>}</span>
        <span>}</span>
        <span>StringBuilder</span> <span>sb</span> <span>=</span> <span>new</span> <span>StringBuilder</span><span>();</span>
        <span>while</span><span>(!</span><span>stack</span><span>.</span><span>isEmpty</span><span>()){</span>
            <span>Node</span> <span>curr</span> <span>=</span> <span>stack</span><span>.</span><span>pop</span><span>();</span>
            <span>char</span> <span>ch</span> <span>=</span> <span>curr</span><span>.</span><span>ch</span><span>;</span>
            <span>int</span> <span>n</span> <span>=</span> <span>curr</span><span>.</span><span>count</span><span>;</span>
            <span>for</span><span>(</span><span>int</span> <span>i</span><span>=</span><span>1</span><span>;</span> <span>i</span><span><=</span><span>n</span><span>;</span> <span>i</span><span>++)</span>
                <span>sb</span><span>.</span><span>append</span><span>(</span><span>ch</span><span>);</span>
        <span>}</span>
        <span>return</span> <span>sb</span><span>.</span><span>reverse</span><span>().</span><span>toString</span><span>();</span>
    <span>}</span>
<span>}</span>
<span>class</span> <span>Node</span><span>{</span>
    <span>char</span> <span>ch</span><span>;</span>
    <span>int</span> <span>count</span><span>;</span>
    <span>Node</span><span>(</span><span>char</span> <span>ch</span><span>,</span> <span>int</span> <span>count</span><span>){</span>
        <span>this</span><span>.</span><span>ch</span> <span>=</span> <span>ch</span><span>;</span>
        <span>this</span><span>.</span><span>count</span> <span>=</span> <span>count</span><span>;</span>
    <span>}</span>
<span>}</span>
<span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>String</span> <span>removeDuplicates</span><span>(</span><span>String</span> <span>s</span><span>,</span> <span>int</span> <span>k</span><span>)</span> <span>{</span>

        <span>Stack</span><span><</span><span>Node</span><span>></span> <span>stack</span> <span>=</span> <span>new</span> <span>Stack</span><span><>();</span>

        <span>for</span><span>(</span><span>char</span> <span>c</span> <span>:</span> <span>s</span><span>.</span><span>toCharArray</span><span>()){</span>
            <span>if</span><span>(!</span><span>stack</span><span>.</span><span>isEmpty</span><span>()</span> <span>&&</span> <span>stack</span><span>.</span><span>peek</span><span>().</span><span>ch</span><span>==</span><span>c</span><span>){</span>
                <span>if</span><span>(++</span><span>stack</span><span>.</span><span>peek</span><span>().</span><span>count</span><span>==</span><span>k</span><span>)</span>
                    <span>stack</span><span>.</span><span>pop</span><span>();</span>
            <span>}</span>
            <span>else</span><span>{</span>
                <span>stack</span><span>.</span><span>push</span><span>(</span><span>new</span> <span>Node</span><span>(</span><span>c</span><span>,</span> <span>1</span><span>));</span>
            <span>}</span>
        <span>}</span>


        <span>StringBuilder</span> <span>sb</span> <span>=</span> <span>new</span> <span>StringBuilder</span><span>();</span>

        <span>while</span><span>(!</span><span>stack</span><span>.</span><span>isEmpty</span><span>()){</span>
            <span>Node</span> <span>curr</span> <span>=</span> <span>stack</span><span>.</span><span>pop</span><span>();</span>
            <span>char</span> <span>ch</span> <span>=</span> <span>curr</span><span>.</span><span>ch</span><span>;</span>
            <span>int</span> <span>n</span> <span>=</span> <span>curr</span><span>.</span><span>count</span><span>;</span>

            <span>for</span><span>(</span><span>int</span> <span>i</span><span>=</span><span>1</span><span>;</span> <span>i</span><span><=</span><span>n</span><span>;</span> <span>i</span><span>++)</span>
                <span>sb</span><span>.</span><span>append</span><span>(</span><span>ch</span><span>);</span>
        <span>}</span>


        <span>return</span> <span>sb</span><span>.</span><span>reverse</span><span>().</span><span>toString</span><span>();</span>
    <span>}</span>
<span>}</span>

<span>class</span> <span>Node</span><span>{</span>
    <span>char</span> <span>ch</span><span>;</span>
    <span>int</span> <span>count</span><span>;</span>
    <span>Node</span><span>(</span><span>char</span> <span>ch</span><span>,</span> <span>int</span> <span>count</span><span>){</span>
        <span>this</span><span>.</span><span>ch</span> <span>=</span> <span>ch</span><span>;</span>
        <span>this</span><span>.</span><span>count</span> <span>=</span> <span>count</span><span>;</span>
    <span>}</span>
<span>}</span>
class Solution {
    public String removeDuplicates(String s, int k) {

        Stack<Node> stack = new Stack<>();

        for(char c : s.toCharArray()){
            if(!stack.isEmpty() && stack.peek().ch==c){
                if(++stack.peek().count==k)
                    stack.pop();
            }
            else{
                stack.push(new Node(c, 1));
            }
        }


        StringBuilder sb = new StringBuilder();

        while(!stack.isEmpty()){
            Node curr = stack.pop();
            char ch = curr.ch;
            int n = curr.count;

            for(int i=1; i<=n; i++)
                sb.append(ch);
        }


        return sb.reverse().toString();
    }
}

class Node{
    char ch;
    int count;
    Node(char ch, int count){
        this.ch = ch;
        this.count = count;
    }
}

Enter fullscreen mode Exit fullscreen mode

Thanks for reading 🙂
Feel free to comment and like the post if you found it helpful
Follow for more 🤝 && Happy Coding

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7

原文链接：Remove All Adjacent Duplicates in String II | LeetCode | Java