Question

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$.

class Solution:
  def removeDuplicates(self, s: str, k: int) -> str:
    t = []
    i, n = 0, len(s)
    while i < n:
      j = i
      while j < n and s[j] == s[i]:
        j += 1
      cnt = j - i
      cnt %= k
      if t and t[-1][0] == s[i]:
        t[-1][1] = (t[-1][1] + cnt) % k
        if t[-1][1] == 0:
          t.pop()
      elif cnt:
        t.append([s[i], cnt])
      i = j
    ans = [c * v for c, v in t]
    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
}

Solution 2

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)