1209. Remove All Adjacent Duplicates in String II

Given a string s, 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 <= 10^5
  • 2 <= k <= 10^4
  • s only contains lower case English letters.

Rust Solution

struct Solution;

impl Solution {
    fn remove_duplicates(s: String, k: i32) -> String {
        let mut stack: Vec<(char, usize)> = vec![];
        for c in s.chars() {
            if let Some(top) = stack.pop() {
                if top.0 != c {
                    stack.push(top);
                    stack.push((c, 1));
                } else {
                    if (top.1 + 1) != k as usize {
                        stack.push((c, top.1 + 1));
                    }
                }
            } else {
                stack.push((c, 1));
            }
        }
        let mut res = "".to_string();
        for p in stack {
            for _ in 0..p.1 {
                res.push(p.0);
            }
        }
        res
    }
}

#[test]
fn test() {
    let s = "abcd".to_string();
    let k = 2;
    let res = "abcd".to_string();
    assert_eq!(Solution::remove_duplicates(s, k), res);
    let s = "deeedbbcccbdaa".to_string();
    let k = 3;
    let res = "aa".to_string();
    assert_eq!(Solution::remove_duplicates(s, k), res);
    let s = "pbbcggttciiippooaais".to_string();
    let k = 2;
    let res = "ps".to_string();
    assert_eq!(Solution::remove_duplicates(s, k), res);
}

Having problems with this solution? Click here to submit an issue on github.