1209. Remove All Adjacent Duplicates in String II

Description

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 <= 105
• 2 <= k <= 104
• s only contains lowercase English letters.

Solutions

Solution 1: Stack

We can traverse the string \(s\), maintaining a stack that stores the characters and their occurrence counts. When traversing to character \(c\), if the character at the top of the stack is the same as \(c\), we increment the count of the top element by one; otherwise, we push the character \(c\) and count \(1\) into the stack. When the count of the top element equals \(k\), we pop the top element from the stack.

After traversing the string \(s\), the elements remaining in the stack form the final result. We can pop the elements from the stack one by one, concatenate them into a string, and that's our answer.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the string \(s\).

Python3JavaC++Go

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stk = []
        for c in s:
            if stk and stk[-1][0] == c:
                stk[-1][1] = (stk[-1][1] + 1) % k
                if stk[-1][1] == 0:
                    stk.pop()
            else:
                stk.append([c, 1])
        ans = [c * v for c, v in stk]
        return "".join(ans)

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();
    }
}

class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<pair<char, int>> stk;
        for (char& c : s) {
            if (stk.size() && stk.back().first == c) {
                stk.back().second = (stk.back().second + 1) % k;
                if (stk.back().second == 0) {
                    stk.pop_back();
                }
            } else {
                stk.push_back({c, 1});
            }
        }
        string ans;
        for (auto [c, v] : stk) {
            ans += string(v, c);
        }
        return ans;
    }
};

func removeDuplicates(s string, k int) string {
    stk := []pair{}
    for _, c := range s {
        if len(stk) > 0 && stk[len(stk)-1].c == c {
            stk[len(stk)-1].v = (stk[len(stk)-1].v + 1) % k
            if stk[len(stk)-1].v == 0 {
                stk = stk[:len(stk)-1]
            }
        } else {
            stk = append(stk, pair{c, 1})
        }
    }
    ans := []rune{}
    for _, e := range stk {
        for i := 0; i < e.v; i++ {
            ans = append(ans, e.c)
        }
    }
    return string(ans)
}

type pair struct {
    c rune
    v int
}

Comments