Leetcode 1209: Remove All Adjacent Duplicates in String II
You are given a string s and an integer k. A k duplicate removal consists of selecting k adjacent and equal letters from the string and removing them, causing the left and the right side of the deleted substring to concatenate together. Repeat this operation until no more such removals are possible. Return the final string after all removals are done.
Problem
Approach
Steps
Complexity
Input: You are given a string s and an integer k.
Example: Input: s = "aabbcc", k = 2
Constraints:
• 1 <= s.length <= 10^5
• 2 <= k <= 10^4
• s consists of lowercase English letters only.
Output: Return the final string after all k duplicate removals have been made.
Example: Output: ""
Constraints:
Goal: The goal is to continuously remove adjacent duplicate letters from the string until no more removals can be made.
Steps:
• Iterate through the string and check for k adjacent equal letters.
• Whenever such a substring is found, remove it and concatenate the remaining parts of the string.
• Repeat this process until no more substrings can be removed.
Goal: The input string s is guaranteed to contain only lowercase English letters and to meet the specified length and k values.
Steps:
• 1 <= s.length <= 10^5
• 2 <= k <= 10^4
• s only contains lowercase English letters.
Assumptions:
• The string s may contain substrings with duplicate characters that need to be removed.
• The solution should handle cases where there are no substrings to remove, as well as when all characters can be removed.
• Input: Input: s = "aabbcc", k = 2
• Explanation: Since the string contains only pairs of identical characters, all of them will be removed, leaving the string empty.
• Input: Input: s = "aaaabbbcccddeee", k = 3
• Explanation: After removing 'aaa', 'bbb', 'ccc', and 'ddd', the string reduces to 'ddee'.
Approach: We can use a stack-based approach to efficiently remove duplicate substrings from the string. The stack will help us keep track of consecutive characters and their counts, allowing us to easily identify and remove substrings of length k.
Observations:
• A stack can be used to keep track of characters and their counts.
• When a character appears k times consecutively, it can be removed.
• The stack will help in managing the characters and removing the substrings efficiently without needing to traverse the string multiple times.
Steps:
• Initialize a stack to keep track of characters and their counts.
• Iterate through the string, updating the stack as characters are encountered.
• If a character's count reaches k, remove it from the stack.
• After processing the string, construct the final result from the stack.
Empty Inputs:
• The string should never be empty as per the constraints.
Large Inputs:
• The algorithm must handle large strings efficiently, up to a length of 10^5.
Special Values:
• Consider cases where no duplicates are found or where the entire string consists of the same character.
Constraints:
• The solution should efficiently handle the maximum possible input size.
string removeDuplicates(string s, int k) {
vector<pair<int, char>> stk = {{0, '#'}};
for(char c : s) {
if(stk.back().second != c)
stk.push_back({1, c});
else if(++stk.back().first == k)
stk.pop_back();
}
string res;
for(auto x: stk)
res.append(x.first, x.second);
return res;
}
1 : Function Definition
string removeDuplicates(string s, int k) {
Define the function `removeDuplicates` which takes a string `s` and an integer `k` as inputs. The goal is to remove adjacent characters that appear consecutively `k` times.
2 : Stack Initialization
vector<pair<int, char>> stk = {{0, '#'}};
Initialize a stack `stk` that will hold pairs of integers and characters. The stack starts with a dummy pair `{0, '#'}` to simplify the logic of checking the first character.
3 : Loop Through Input String
for(char c : s) {
Start a loop that iterates over each character `c` in the input string `s`.
4 : Check for Non-Matching Character
if(stk.back().second != c)
If the current character `c` does not match the character at the top of the stack, proceed to the next step.
5 : Push New Character to Stack
stk.push_back({1, c});
Push a new pair `{1, c}` to the stack, indicating that the character `c` has appeared once consecutively.
6 : Check for Consecutive Duplicates
else if(++stk.back().first == k)
If the current character `c` matches the top of the stack, increment the count of consecutive occurrences. If the count reaches `k`, proceed to the next step.
7 : Pop the Stack
stk.pop_back();
Pop the top element from the stack, as the character has occurred `k` times consecutively and should be removed.
8 : Result String Initialization
string res;
Initialize an empty string `res` to store the final result after removing the duplicates.
9 : Rebuild Result String
for(auto x: stk)
Iterate over the stack `stk` to rebuild the result string. Each element in the stack is a pair, where the first element is the count and the second element is the character.
10 : Append Characters to Result
res.append(x.first, x.second);
For each pair in the stack, append the character `x.second` to the result string `res`, `x.first` times.
11 : Return Final Result
return res;
Return the result string `res`, which contains the characters after removing all adjacent duplicates that appeared consecutively `k` times.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the string. Each character is processed at most twice.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n), as we need to store the stack to manage the characters and their counts.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus