algoadvance

Leetcode 316. Remove Duplicate Letters

Problem Statement

The task is to remove duplicate letters from a given string s so that every letter appears only once, and we must make sure our result is the smallest in lexicographical order among all possible results.

Example:

Input: s = "bcabc"
Output: "abc"

Input: s = "cbacdcbc"
Output: "acdb"

Clarifying Questions

  1. Can the input string contain non-alphabetic characters?
    • No, the input string s will consist of lowercase English letters only.
  2. What should be the return type?
    • The function should return a string.
  3. How long can the input string be?
    • The length of the input string s will be at least 1 and at most 1000.

Strategy

To solve this problem, we can use a greedy approach with a stack data structure to build the resultant string:

  1. Frequency Count: First, count the frequency of each character in the input string to know how many times each character appears.
  2. Stack Use: Use a stack to build the result string.
  3. Visited Set: Maintain a set to check if a character is already in the stack to avoid duplicates.
  4. Greedy Choice: Iterate over the string and for each character:
    • Decrease its frequency in the counter.
    • If the character is already in the stack, continue.
    • While the stack is not empty and the top of the stack is greater than the current character and the top character appears later in the string (frequency count > 0), pop the stack.
    • Push the current character onto the stack.
  5. Construct Result: Finally, join the stack contents to form the resultant string.

Code

import java.util.*;

public class Solution {
    public String removeDuplicateLetters(String s) {
        int[] freq = new int[26]; // Frequency of each character
        boolean[] visited = new boolean[26]; // Whether the character is in stack or not
        
        // Calculate the frequency of each character
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            freq[c - 'a']--; // Decrease frequency each time we encounter the character
            
            // If char is already in stack, continue
            if (visited[c - 'a']) continue;
            
            // Remove characters from the stack to maintain lexicographical order
            while (!stack.isEmpty() && stack.peek() > c && freq[stack.peek() - 'a'] > 0) {
                visited[stack.pop() - 'a'] = false;
            }
            
            stack.push(c);
            visited[c - 'a'] = true;
        }
        
        // Build the resultant string from the stack
        StringBuilder result = new StringBuilder();
        for (char c : stack) {
            result.append(c);
        }
        
        return result.toString();
    }
}

Time Complexity

Overall, the time complexity is O(n), making this approach efficient for the problem constraints.

Space Complexity

The space complexity is O(1) if we only consider the additional data structures used (frequency array, visited array, and stack), since the total auxiliary space used is constant concerning the alphabet size (26). However, taking into account the stack and result, it is O(n), where n is the length of the input string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI