algoadvance

Leetcode 316. Remove Duplicate Letters

Problem Statement

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. You must ensure that you keep the relative order of the characters the same as in the given string.

Clarifying Questions

1. Range of Input:
   • What is the length range of the input string s?
   • Are there any constraints on the characters in the string (e.g., lowercase English letters only)?
2. Output:
   • Should the function return the smallest possible string in terms of lexicographical order even if it means characters appear non-contiguously?
   • Is the output case-sensitive?

Assumptions Based on Typical Problems:

1. The string s consists of lowercase English letters only.
2. The length of s can range from 1 to 10^4.
3. The function needs to maintain the order of characters as much as possible while ensuring the final string is in the smallest lexicographical order.

Strategy

• Use a greedy algorithm combined with a monotonic stack to construct the result.
• Maintain a count of each character (using an array or hashmap).
• Use a stack to build the result string such that the top of the stack is the smallest possible character.
• Ensure that each character appears only once in the resulting string by using a boolean array.

Steps

1. Count the frequency of each character in the string.
2. Initialize a stack to keep track of the resulting characters.
3. Use a set (or boolean array) to determine if a character is already in the stack.
4. Iterate over each character in the string:
   • Decrement its frequency count.
   • If the character is already in the stack, continue to the next character.
   • If the current character is smaller than the character at the top of the stack and the top character still has occurrences left in the remaining string, pop the character from the stack.
   • Add the current character to the stack and mark it as used.
5. Construct the result from the stack.

Code

#include <string>
#include <vector>
#include <stack>
#include <unordered_map>
#include <algorithm>

std::string removeDuplicateLetters(std::string s) {
    std::unordered_map<char, int> charCount;
    std::unordered_map<char, bool> inStack;
    for (char c : s) {
        charCount[c]++;
    }

    std::stack<char> st;
    for (char c : s) {
        charCount[c]--;
        
        if (inStack[c]) continue;

        while (!st.empty() && st.top() > c && charCount[st.top()] > 0) {
            inStack[st.top()] = false;
            st.pop();
        }     
        
        st.push(c);
        inStack[c] = true;
    }

    std::string result;
    while (!st.empty()) {
        result.push_back(st.top());
        st.pop();
    }
    
    std::reverse(result.begin(), result.end());
    
    return result;
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string s, for the following reasons:

• Counting the frequency of each character takes O(n).
• Iterating through the characters and handling the stack operations also takes O(n) in total since each character is pushed and popped from the stack at most once.

The solution is space-efficient relative to the input size.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?