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.
Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete. All are unique letters.
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"
Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"
Constraints:
- 1 <= s.length <= 105
- 2 <= k <= 105
- s only contains lowercase English letters.
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.
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