
Problem Statement
The task involves manipulating a given string s
by removing any duplicate letters. The goal is to ensure each character appears only once, and moreover, the resulting string must be the smallest lexicographically. Lexicographical order is akin to dictionary order, which means "abc" is smaller than "acb". The given string can have a length ranging from 1 to 10,000, and it contains only lowercase English letters. This task tests one's ability to perform string manipulations and understanding of lexicographical orderings efficiently, especially given potentially large input sizes.
Examples
Example 1
Input:
s = "bcabc"
Output:
"abc"
Example 2
Input:
s = "cbacdcbc"
Output:
"acdb"
Constraints
1 <= s.length <= 104
s
consists of lowercase English letters.
Approach and Intuition
Given the nature of this problem, the goal is not just to remove duplicates but to organize the remaining characters in the smallest possible lexicographical sequence.
One intuitive approach is to use a stack to keep track of the final sequence of characters in resulted string and utilize a set or a hash table to check if a character has already been added or not.
General intuition and logic flow:
- Traverse each character of the string.
- Maintain a count of each character's occurrences in the string.
- Utilize a greedy algorithm to decide if placing the current character will result in a smaller lexicographical order. This involves:
- Checking if the current character is smaller than the last character in the result stack and deciding whether or not the last character can appear later in the string.
- If the last character can appear later (i.e., if its count isn't zero), it might be beneficial to remove it from the stack for a potentially smaller lexicographical order result.
- Use a boolean array or a set to keep track of characters that are already added to the result stack to avoid duplications.
Detailed Operations:
- For each character, reduce its count (which was precalculated at the beginning).
- If the character is not already in the stack, compare it with the end of the current stack.
- Pop characters from the stack if it is greater than the current character and still has occurrences left in the rest of the string.
- Push the current character onto the stack if it's not already there.
This approach leverages the power of the stack data structure to maintain the smallest lexicographical order while ensuring that each character is treated with its occurrence due limit, making an effective and efficient solution to the required problem.
Solutions
- Java
class Solution {
public String uniqueLetters(String str) {
Stack<Character> characters = new Stack<>();
// Keeps track of characters added to the result
HashSet<Character> tracked = new HashSet<>();
// Tracks the last index of each character
HashMap<Character, Integer> lastIndex = new HashMap<>();
for(int index = 0; index < str.length(); index++) lastIndex.put(str.charAt(index), index);
for(int index = 0; index < str.length(); index++){
char character = str.charAt(index);
// Add character if not already added to maintain uniqueness
if (!tracked.contains(character)){
// Ensure the smallest lexicographical order is maintained
while(!characters.isEmpty() && character < characters.peek() && lastIndex.get(characters.peek()) > index){
tracked.remove(characters.pop());
}
tracked.add(character);
characters.push(character);
}
}
StringBuilder result = new StringBuilder(characters.size());
for (Character ch : characters) result.append(ch.charValue());
return result.toString();
}
}
In this solution summary, the Java program addresses the problem of removing duplicate letters from a string while ensuring the resultant unique letters maintain the smallest lexicographical order.
- Initialize a
Stack
namedcharacters
to store the characters in the required order. - Create a
HashSet
namedtracked
to keep track of characters that are already added tocharacters
stack. - Use a
HashMap
namedlastIndex
to map each character to its last occurrence index in the string. This helps to determine if a character can still appear later in the string.
For each character in the string:
- Check if it has not been added to the stack (using
tracked
). If not already added:- While the stack is not empty and the current character is smaller than the top of the stack (indicating a smaller lexicographical order) and the character at the top can still appear later in the string (determined using
lastIndex
), pop the top character. Remove this character fromtracked
. - Add the current character to
tracked
and push it onto the stack.
- While the stack is not empty and the current character is smaller than the top of the stack (indicating a smaller lexicographical order) and the character at the top can still appear later in the string (determined using
After processing all characters:
- Construct the result string by popping all characters from the stack. This ensures that the characters are appended to the resultant string in the correct order.
Return the resultant string which now contains unique letters sorted in the smallest lexicographical order which was achieved while iterating through the original string only once.
No comments yet.