Remove All Adjacent Duplicates in String II

Share

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. All are unique letters.
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:

Contents

Solution 1 - Using a Stack

In this approach, we will loop through each character and if keep a count of consecutive characters count, i.e. if the previous character and current character are same will increment the character count by 1, ad add this mapping into a Stack, when the count becomes k, we wil remove the top element from stack and continue the process. At the end return a string with remaining characters and their count.

Java
import java.util.Stack;

public class RemoveAllAdjacentDuplicatesInStringII {

    static String removeDuplicates(String s, int k) {
        Stack<int[]> stack = new Stack<>();
        for(char c: s.toCharArray()) {
            if(!stack.isEmpty() && stack.peek()[0] == c){
                stack.peek()[1]++;
            } else {
                stack.push(new int[]{c, 1});
            }
            if(stack.peek()[1] == k) {
                stack.pop();
            }
        }
        StringBuilder sb = new StringBuilder();
        stack.forEach(entry->sb.append(Character.toString(entry[0]).repeat(entry[1])));
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(removeDuplicates("abcd", 3));
        System.out.println(removeDuplicates("deeedbbcccbdaa", 3));
        System.out.println(removeDuplicates("pbbcggttciiippooaais", 2));
    }
}
Complexity Analysis:

Time complexity: Time complexity for the solution will be O(n) where n is the length of input string s.
Space complexity: O(n) for storing elements into stack.

Above implementations source code can be found at GitHub link for Java code