Lexicographically Largest Distinct-Letter Subsequence
Reported by candidates from Navan's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The Navan OA reported in May 2023 has a trap that kills the obvious approach: you can't just sort the letters descending, and you can't just grab the biggest letter you see. Order has to survive, and every distinct letter has to appear exactly once. This is the lexicographically largest distinct-letter subsequence, and it's a monotonic stack problem in disguise. If you've seen the smallest-result version, this is the mirror image. If you haven't, the stack idea takes ten minutes to learn and a lot longer to rediscover under a timer. StealthCoder sits invisibly on your screen during the live assessment as a safety net if your mind goes blank on the pop condition.
The problem
Given a lowercase string s, remove characters so that every distinct letter appears exactly once. The remaining characters must preserve their original relative order. Return the lexicographically largest possible result. Function largestUniqueLetters(s: String) → String Examples Example 1 s = "bcabc" return = "cab" The subsequence cab contains each distinct letter once and is lexicographically largest. Example 2 s = "cbacdcbc" return = "cbad" Keeping the early c and b allows the largest valid prefix. Example 3 s = "bbcaac" return = "bca" The best unique-letter subsequence is bca. Constraints 1 ≤ s.length ≤ 100000. s contains only lowercase English letters.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Track the last index of every letter and a set of letters already in the stack. Walk the string. If the current letter is already in the stack, skip it. Otherwise, while the stack top is smaller than the current letter and that top appears again later, pop it and unmark it. Then push the current letter. That's the whole algorithm, and it runs in O(n) because each character is pushed and popped at most once. The pitfall is the 'appears later' check. Pop a letter that never returns and you lose it permanently, which breaks the one-of-each rule. The second pitfall is forgetting to skip duplicates, which wrecks example 2 (cbacdcbc becomes cbad). Flip the comparison from the smallest version and you're done. If the pop condition slips your mind mid-assessment, StealthCoder can hand you the working version live while you keep typing.
If this hits your live OA and you blank, StealthCoder solves it in seconds, invisible to the proctor.
You can drill Lexicographically Largest Distinct-Letter Subsequence cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Navan's OA.
Navan reuses patterns across OAs. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Lexicographically Largest Distinct-Letter Subsequence FAQ
What's the trick for the Navan largest unique-letter subsequence problem?+
Use a monotonic stack with last-occurrence indexes. For each new letter, pop smaller letters off the top only if they show up again later. Skip any letter already in the stack. The stack ends up as the lexicographically largest result with each letter once.
Why does sorting letters descending fail?+
Sorting ignores original order, and the result must be a subsequence of s. For bbcaac, descending gives cba, but c at index 2 has no a or b after it that fits. The right answer is bca. Order constraints are the whole point.
How hard is this one really?+
Medium. The code is about 15 lines, but the pop condition is easy to get wrong. If you know the remove-duplicate-letters stack pattern, it's a flipped comparison. If you don't, expect to burn time on brute force ideas first.
What edge cases should I test before submitting?+
Test a single character, a string of one repeated letter like aaaa, an already descending string, and example 2 (cbacdcbc). The last one catches missing duplicate skips. Also confirm the last-index map is built before the main loop, not during it.
How do I prepare for this in 48 hours?+
Learn the monotonic stack with a last-index map and a seen set. Write it once from memory, then flip the comparison for the largest version. Trace examples 1 and 2 by hand. That's enough for this pattern, and it shows up in other subsequence-ordering questions too.