Remove Duplicate Letters

MediumStackmonotonic stack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given a string s of lowercase English letters, delete characters so that every distinct letter of s appears **exactly once**, keeping the surviving characters in their original order. Among all such results, return the one that is smallest in lexicographical order. Target O(n) time with O(1) extra space beyond the 26-letter alphabet.

Examples

Input: s = "bcabc"
Output: "abc"
Keeping the a at index 2 followed by b and c gives "abc", the smallest option.
Input: s = "cbacdcbc"
Output: "acdb"
Every other subsequence using each of a, b, c, d once is lexicographically larger.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More monotonic stack problems