Remove Duplicate Letters

Updated on 03 July, 2025
Remove Duplicate Letters header image

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

  • Java
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 named characters to store the characters in the required order.
  • Create a HashSet named tracked to keep track of characters that are already added to characters stack.
  • Use a HashMap named lastIndex 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 from tracked.
    • Add the current character to tracked and push it onto the stack.

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.

Comments

No comments yet.