1209. Remove All Adjacent Duplicates in String II

Description

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.

Constraints

• 1 <= s.length <= 10^5

• 2 <= k <= 10^4

• s only contains lower case English letters.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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"

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public String removeDuplicates(String s, int k) {
        for(int i = 1, count = 1; i < s.length(); i++) {
            count = (s.charAt(i) == s.charAt(i-1))? count+1: 1;
            if(count == k) {
                s = removeDuplicates(s.substring(0, i-k+1)+s.substring(i+1), k);
            }
        }
        return s;
    }
}

Follow up