Katkat
Back

Remove Duplicate Letters Lexicographically

ByteDanceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use a monotonic stack combined with frequency tracking to construct a specific subsequence while maintaining lexicographical order.

Problem Statement

Given a string s, remove all duplicate letters such that every letter appears exactly once and the resulting string is the lexicographically smallest possible string among all valid results.

Function Signature

def remove_duplicate_letters(s: str) -> str:

Constraints

  • 1 <= s.length <= 10^4
  • s consists of lowercase English letters.

Examples

Example 1: Input: s = "bcabc" Output: "abc" Explanation: The distinct characters are 'a', 'b', and 'c'. The lexicographically smallest subsequence is "abc".

Example 2: Input: s = "cbacdcbc" Output: "acdb" Explanation: Possible subsequences include "cbad", "acdb", etc. "acdb" is the smallest lexicographical arrangement.

Edge Cases

  • String with all identical characters (e.g., "aaaa").
  • String with all unique characters.
  • String where the smallest character appears only at the end.

Hints

Hint 1

Keep track of the last occurrence index of each character to know if it's safe to discard a character currently in your stack.

Hint 2

Use a stack to maintain the characters of the result, and only push a character if it is not already present in the stack.

Hint 3

If the current character is smaller than the character at the top of the stack and the top character appears again later in the string, pop it from the stack.

Follow-up questions

  • How would you modify your solution if the requirement was to keep the lexicographically largest subsequence instead?
  • What is the time and space complexity of your approach, and can you explain why it is optimal?
  • How would you handle the problem if the input was a stream of characters rather than a complete string?