LeetCode 1209. Remove All Adjacent Duplicates in String II

原题链接在这里：https://leetcode.com/problems/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.

题解：

Follow the instruction, delete the duplicate, when we have a delete, mark changed as true.

While changed is true, continue.

Time Complexity: O(n^2/k - n). n = s.length(). each level, s becomes n - k, totally there are n/k level.

Space: O(n).

AC Java:

class Solution {
    public String removeDuplicates(String s, int k) {
        if(s == null || s.length() == 0){
            return s;
        }
        
        if(k == 1){
            return "";
        }
        
        boolean changed = true;
        while(changed){
            changed = false;
            StringBuilder sb = new StringBuilder();
            
            int i = 0;
            while(i < s.length()){
                if(i == s.length() - 1 || s.charAt(i) != s.charAt(i + 1)){
                    sb.append(s.charAt(i));
                    i++;
                }else{
                    int j = i + 1;
                    int count = 1;
                    while(j < s.length() && s.charAt(j) == s.charAt(i) && count < k){
                        j++;
                        count++;
                    }
                    
                    if(count < k){
                        sb.append(s.substring(i, j));   
                    }else{
                        changed = true;
                    }
                    
                    i = j;
                }
            }
            
            s = sb.toString();
        }
        
        return s;
    }
}