Remove All Adjacent Duplicates in String II
Given a string s and an integer k, the task is to repeatedly delete k adjacent duplicates till no deletions are possible and then return the final string. On deletion of k adjacent duplicates, the left and right sides of the deleted substring is concatenated together.
Examples:
Input: s = “abcd”, k = 2
Output: “abcd”
Explanation: There’s nothing to delete.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”.
Approach: To solve the problem, follow the below idea:
To solve this problem, we can use a stack to keep track of characters and their counts. The idea is to use the stack to store pairs of characters and their consecutive counts. Whenever we encounter k consecutive characters, we remove them from the stack.
Step-by-step algorithm:
- Initialize a stack that will store pairs of characters and their consecutive counts.
- Iterate through the string:
- For each character, check if the stack is not empty and the top character of the stack is the same as the current character.
- If they are the same, increment the count.
- If the count reaches k, pop the stack.
- If they are not the same, push the current character with a count of 1 onto the stack.
- Construct the resulting string from the stack.
- Return the resulting string.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
string removeDuplicates(string s, int k)
{
// stack to store the character with its count
stack<pair<char, int> > st;
for (char c : s) {
// If the character is same as character at top, increase the count of top character
if (!st.empty() && st.top().first == c) {
st.top().second++;
if (st.top().second == k) {
st.pop();
}
}
// If the character is different from the character at top, push the character to the top
else {
st.push({ c, 1 });
}
}
string result = "";
// Construct the result string
while (!st.empty()) {
result.append(st.top().second, st.top().first);
st.pop();
}
reverse(result.begin(), result.end());
return result;
}
int main()
{
// Example 1
string s1 = "abcd";
int k1 = 2;
cout << removeDuplicates(s1, k1)
<< endl; // Output: "abcd"
return 0;
}
import java.util.*;
public class RemoveDuplicates {
public static String removeDuplicates(String s, int k) {
// Stack to store the character with its count
Deque<Pair> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
// If the character is same as the character at top, increase the count of top character
if (!stack.isEmpty() && stack.peek().character == c) {
stack.peek().count++;
if (stack.peek().count == k) {
stack.pop();
}
}
// If the character is different from the character at top, push the character to the top
else {
stack.push(new Pair(c, 1));
}
}
StringBuilder result = new StringBuilder();
// Construct the result string
while (!stack.isEmpty()) {
Pair p = stack.pop();
for (int i = 0; i < p.count; i++) {
result.append(p.character);
}
}
return result.reverse().toString();
}
public static void main(String[] args) {
// Example 1
String s1 = "abcd";
int k1 = 2;
System.out.println(removeDuplicates(s1, k1)); // Output: "abcd"
}
}
class Pair {
char character;
int count;
Pair(char character, int count) {
this.character = character;
this.count = count;
}
}
// This code is contributed by Shivam Gupta
Output
abcd
Time Complexity: O(n), where n is the length of the string.
Auxiliary Space: O(n)
Related Articles: