grid47 Exploring patterns and algorithms
Oct 6, 2024
6 min read
Solution to LeetCode 316: Remove Duplicate Letters Problem
Given a string ’s’, remove duplicate letters so that every letter appears once and only once. The result should be the smallest lexicographical order among all possible results.
Problem
Approach
Steps
Complexity
Input: The input consists of a string 's' that contains lowercase English letters.
Example: s = 'acdbac'
Constraints:
• 1 <= s.length <= 10^4
• s consists of lowercase English letters.
Output: The output is a string with no duplicate letters, and the smallest lexicographical order.
Example: 'abcd'
Constraints:
• The string should contain unique characters in lexicographical order.
Goal: To remove duplicate characters while ensuring the resulting string is lexicographically smallest.
Steps:
• Traverse the string and count the frequency of each character.
• Maintain a stack to build the result string, ensuring lexicographical order by popping characters from the stack when necessary.
• Ensure that each character is only added once to the result string.
Goal: The solution should work efficiently for strings with lengths up to 10^4.
Steps:
• Ensure that the solution handles large strings efficiently.
• Handle edge cases like strings with only one character or strings that already have unique characters.
Assumptions:
• The input string 's' is guaranteed to contain only lowercase English letters.
• Input: s = 'acdbac'
• Explanation: Removing the duplicate 'a', 'c', and 'b' results in the lexicographically smallest string 'abcd'.
• Input: s = 'zxyzyx'
• Explanation: The lexicographically smallest string without duplicates is 'xyz'.
Approach: To solve this problem, use a greedy algorithm with a stack to ensure that the string is both unique and lexicographically smallest.
Observations:
• The string needs to maintain its smallest lexicographical order while removing duplicates.
• We can use a stack to build the result string, popping elements from the stack when a smaller element appears and is guaranteed to appear later.
Steps:
• Count the frequency of each character in the string.
• Use a stack to build the output string, ensuring that characters are added in lexicographical order.
• For each character in the string, check if it should be added to the stack by comparing it with the top of the stack and checking the frequency of future characters.
Empty Inputs:
• The input will never be empty, as the length of the string is at least 1.
Large Inputs:
• The solution must efficiently handle strings with lengths up to 10^4.
Special Values:
• If the string is already unique, it should be returned unchanged.
Constraints:
• Ensure that the algorithm works in O(n) time to handle the upper constraint.
string removeDuplicateLetters(string s) {
vector<int> frq(26, 0), lidx(26, 0);
for (int i =0; i < s.size(); i++) {
char x = s[i];
frq[x -'a']++;
lidx[x -'a'] = i;
}
vector<bool> seen(26, false);
stack<char> st;
for(int i =0; i < s.size(); i++) {
int cur = s[i] -'a';
if(seen[cur]) continue;
while(st.size() >0&& st.top() > s[i] && i < lidx[st.top() -'a']) {
seen[st.top() -'a'] =false;
st.pop();
}
st.push(s[i]);
seen[cur] =true;
}
string ans ="";
while(st.size() >0) {
ans += st.top();
st.pop();
}
reverse(ans.begin(), ans.end());
return ans;
}
1 : Function Definition
string removeDuplicateLetters(string s) {
This is the function definition, where a string `s` is passed as input.
2 : Initialization
vector<int> frq(26, 0), lidx(26, 0);
Initialize two vectors: `frq` for character frequency and `lidx` for the last index of each character.
3 : Loop
for (int i =0; i < s.size(); i++) {
Iterate through the string `s` to populate the frequency and last index vectors.
4 : Character Processing
char x = s[i];
Extract each character from the string during the iteration.
5 : Frequency Update
frq[x -'a']++;
Increment the frequency of the current character in the `frq` vector.
6 : Last Index Update
lidx[x -'a'] = i;
Update the last index of the current character in the `lidx` vector.
7 : Seen Initialization
vector<bool> seen(26, false);
Initialize a `seen` vector to track whether a character has been added to the result.
8 : Stack Initialization
stack<char> st;
Initialize a stack to build the result string by storing characters.
9 : Loop
for(int i =0; i < s.size(); i++) {
Loop through the string `s` again to build the result string.
10 : Character Conversion
int cur = s[i] -'a';
Convert the current character to its respective index based on the alphabet.
11 : Check if Seen
if(seen[cur]) continue;
If the character has already been added to the result, skip it.
