Description
Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is
the smallest in lexicographical order among all possible results.
Examples:
Example 1:
Input: s = "bcabc"
Output: "abc"
Example 2:
Input: s = "cbacdcbc"
Output: "acdb"Solution in Python
To solve the problem of removing duplicate letters from a string while ensuring that the result is the smallest lexicographical order, we need a well-structured approach that balances keeping track of which characters to include and ensuring the lexicographical order is minimal.
Approach Overview:
- We need to maintain a stack of characters that will represent the final result string.
- Each character will be added to this stack only once. If the character already exists in the stack, we skip it.
- Before adding a character, if the current character is smaller (lexicographically) than the character at the top of the stack, and if the character at the top of the stack appears later in the string again, we can remove the top character and push the current one instead.
- We use a last occurrence map to track the last index where each character appears to help in deciding whether a character can be safely removed and re-added later.
Detailed Steps:
- Track the last occurrence of each character in the string. This will help us know if it’s safe to remove a character from the stack, as we can add it later.
- Use a stack to build the result string.
- Use a set to track which characters are already in the stack, ensuring that each character only appears once in the result.
- Traverse the string character by character:
- If the character is already in the stack, skip it.
- If the character is not in the stack, check whether the current character is smaller than the top of the stack. If the top character of the stack appears again later, we can pop it from the stack and add the current character.
- After processing all characters, the stack will contain the result in lexicographically smallest order.
Python
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
# Step 1: Track the last occurrence of each character
last_occurrence = {char: i for i, char in enumerate(s)}
# Stack to build the final result
stack = []
# Set to keep track of characters already in the stack
in_stack = set()
# Step 2: Traverse each character in the string
for i, char in enumerate(s):
# If the character is already in the stack, skip it
if char in in_stack:
continue
# Step 3: Ensure the stack is in lexicographical order
# Pop characters that are greater than the current character
# and can still appear later in the string
while stack and stack[-1] > char and last_occurrence[stack[-1]] > i:
# Remove the top character from the stack and set
removed_char = stack.pop()
in_stack.remove(removed_char)
# Add the current character to the stack and mark it as used
stack.append(char)
in_stack.add(char)
# Step 4: Return the final result as a string
return ''.join(stack)Explanation of the Code:
- Step 1: Track last occurrence:
- We create a dictionary
last_occurrencethat maps each character to its last index in the string. This will allow us to know if a character can appear again later.
- We create a dictionary
- Step 2: Traverse the string:
- For each character in the string
s, if it is already present in the stack (tracked byin_stack), we skip it because we only need one occurrence of each character.
- For each character in the string
- Step 3: Maintain lexicographical order:
- Before adding a character to the stack, we check the top character of the stack (
stack[-1]). If the top character is greater than the current character and can appear later in the string (last_occurrence[stack[-1]] > i), we pop it from the stack. This ensures that the stack remains lexicographically sorted.
- Before adding a character to the stack, we check the top character of the stack (
- Step 4: Build the result:
- After processing all characters, the stack contains the result string, which is in lexicographically smallest order. We return the stack as a string by joining the characters.
Solution in C++
C++
class Solution {
public:
string removeDuplicateLetters(string s) {
// Step 1: Track the last occurrence of each character
vector<int> lastOccurrence(26, 0); // Store the last occurrence of each character ('a' to 'z')
for (int i = 0; i < s.length(); ++i) {
lastOccurrence[s[i] - 'a'] = i; // Map character to its last index
}
vector<bool> inStack(26, false); // To track if character is already in the stack
stack<char> resultStack; // This will store the result characters
// Step 2: Traverse the string
for (int i = 0; i < s.length(); ++i) {
char currChar = s[i];
// If the character is already in the stack, skip it
if (inStack[currChar - 'a']) {
continue;
}
// Step 3: Ensure lexicographical order by popping from stack if possible
while (!resultStack.empty() && resultStack.top() > currChar && lastOccurrence[resultStack.top() - 'a'] > i) {
inStack[resultStack.top() - 'a'] = false; // Mark the character as removed
resultStack.pop(); // Remove the character from the stack
}
// Add the current character to the stack
resultStack.push(currChar);
inStack[currChar - 'a'] = true; // Mark it as added to the stack
}
// Step 4: Build the final result string from the stack
string result;
while (!resultStack.empty()) {
result = resultStack.top() + result; // Pop characters and add to result
resultStack.pop();
}
return result;
}
};Solution in Javascript
JavaScript
var removeDuplicateLetters = function(s) {
// Create a stack to store the resulting characters in the correct order
const stack = [];
// Set to keep track of characters already in the stack (to avoid duplicates)
const seen = new Set();
// Create a map to count the occurrences of each character in the string
const lastOccurrence = {};
// Fill the map with the index of the last occurrence of each character
for (let i = 0; i < s.length; i++) {
lastOccurrence[s[i]] = i;
}
// Iterate through the string
for (let i = 0; i < s.length; i++) {
const char = s[i];
// If the character is already in the result stack, skip it
if (seen.has(char)) {
continue;
}
// Check if the current character can be added in a lexicographically smaller way
// While the stack is not empty, and the top of the stack is greater than the current character,
// and the top of the stack character appears later in the string (so it can be added again later),
// we pop the stack (remove the larger character)
while (stack.length > 0 && stack[stack.length - 1] > char && lastOccurrence[stack[stack.length - 1]] > i) {
// Remove the top character from the stack and from the 'seen' set
seen.delete(stack.pop());
}
// Push the current character to the stack and mark it as seen
stack.push(char);
seen.add(char);
}
// Convert the stack to a string and return it as the result
return stack.join('');
};Solution in Java
Java
class Solution {
public String removeDuplicateLetters(String s) {
// Stack to store the result characters in lexicographical order
Stack<Character> stack = new Stack<>();
// Set to keep track of characters already in the stack (to avoid duplicates)
Set<Character> seen = new HashSet<>();
// Map to keep track of the last occurrence index of each character in the string
Map<Character, Integer> lastOccurrence = new HashMap<>();
// Fill the map with the index of the last occurrence of each character
for (int i = 0; i < s.length(); i++) {
lastOccurrence.put(s.charAt(i), i);
}
// Iterate through each character in the string
for (int i = 0; i < s.length(); i++) {
char currentChar = s.charAt(i);
// If the character is already in the result stack, skip it
if (seen.contains(currentChar)) {
continue;
}
// Ensure the characters in the stack are in lexicographically smallest order
// While the stack is not empty, and the top of the stack is greater than the current character,
// and the top of the stack character appears later in the string (so it can be added again later),
// we pop the stack (remove the larger character)
while (!stack.isEmpty() && stack.peek() > currentChar && lastOccurrence.get(stack.peek()) > i) {
// Remove the character from the stack and the 'seen' set
seen.remove(stack.pop());
}
// Push the current character to the stack and mark it as seen
stack.push(currentChar);
seen.add(currentChar);
}
// Build the result from the characters in the stack
StringBuilder result = new StringBuilder();
for (char ch : stack) {
result.append(ch);
}
// Convert the StringBuilder to a string and return it
return result.toString();
}
}