Remove Duplicate Letters

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.

1. 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.

2. 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.

3. 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

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();
    }
}