Lexicographically Largest Subsequence

Lexicographically Largest Subsequence asks you to pick characters from a string (keeping their order) so the result is as large as possible in dictionary order. The whole problem collapses to a single greedy scan once you flip your perspective and read the string backwards.

The slow way first

You could generate every subsequence and take the maximum — but there are 2^n of them, so that is hopeless for anything but tiny strings.

The question to ask: what makes one subsequence beat another? In dictionary order, the first character dominates everything after it. So the answer must start with the single largest character in the string. After that character, the answer must start with the largest character that appears to its right, and so on. Each chosen character must be the biggest of everything remaining after the previous pick.

The idea: keep characters that never drop

That "biggest from here onward" rule is awkward going left to right, but it becomes trivial right to left. Scan from the end. Keep a running best = the largest character seen so far (which, going backwards, is the largest character to the right). A character belongs in the answer exactly when it is greater than or equal to best — because nothing to its right is bigger than it.

Because we walked backwards, the kept characters come out in reverse order, so the final step is just to reverse the list.

Walk through it

Step through the animation. The pointer i moves right to left. For "abdca": a is kept (best = a), c beats it (best = c), d beats that (best = d), then b and a are both smaller than d and get dropped. We kept [a, c, d]; reversing gives "dca".

Pseudocode

kept = empty list
best = "" (smaller than any character)
for ch in s read from right to left:
    if ch >= best:
        best = ch
        append ch to kept
reverse kept
return kept joined into a string

The Python solution

def largest_subsequence(s):
    kept = []
    best = ""
    for ch in reversed(s):
        if ch >= best:
            best = ch
            kept.append(ch)
    kept.reverse()
    return "".join(kept)

• best is the largest character seen so far in the backward scan — equivalently, the largest character to the right of where we are.
• reversed(s) walks the string from the last character to the first.
• The test ch >= best is the whole greedy decision: keep ch only if nothing to its right is bigger.
• We use >= (not >) so that ties are kept — equal characters later in the string still belong in the largest subsequence.
• Because we built kept backwards, kept.reverse() puts it back into original order before we join it.

Complexity

We touch each character once and keep at most n of them, so the work is linear and the extra space is the output list.

When this pattern shows up

Practice