How do you solve Reverse Shuffle Merge using the Greedy Monotonic Stack over reverse(A) (Optimal) approach?

When to use it: The answer they want — 'smallest count-valid subsequence of reverse(A) via a count-aware monotonic stack'. Scan `A` from right to left (i.e. left-to-right over `reverse(A)`), building `s` on a stack. Maintain three 26-slot arrays: `need[c] = count[c]/2`, `used[c]` (how many `c`'s are currently on the stack), and `remaining[c]` (how many `c`'s are still unprocessed, to the left). **Per character `c` (after decrementing `remaining[c]`):** - If `used[c] == need[c]`, we already have all the `c`'s we need — **skip** it (taking more would exceed the multiset). - Otherwise, before pushing, **pop** any stack-top `t` that is *larger* than `c` **provided** `need[t] - used[t] < remaining[t]`. That condition means: even after removing this `t` from the stack, enough `t`'s remain to the left to re-collect later and still meet `need[t]`. Popping a larger character that sits before `c` makes the result lexicographically smaller. - Then **push** `c` and increment `used[c]`. **Why right-to-left.** The recovered characters, read in A's natural order, spell `reverse(s)`. Reading A backwards is reading `reverse(A)` forwards, so the stack we accumulate spells `s` directly — no final reversal. The `"aabb" → "ba"` case is the proof: a left-to-right greedy would wrongly emit `"ab"`. **Why the pop guard is exactly `need[t] - used[t] = need[t] - used[t] + 1`, i.e. `need[t] - used[t] < remaining[t]`. If that fails, this `t` is irreplaceable — keep it and stop popping. **Why each character is pushed/popped at most once** gives the linear bound — the inner while-loop is amortised O(1). Time complexity: O(n). Space complexity: O(1).

Loading…

hardStrings0Sometimes asked

Reverse Shuffle Merge

Q: How do you solve Reverse Shuffle Merge using the Brute Force — Search All Valid Subsequences approach?

When to use it: Use it to establish what 'valid s' means and why the answer is a smallest subsequence, then note the search is exponential. Make the validity condition explicit, then search. A valid `s` uses exactly `need[c] = count[c]/2` of each character and must be a subsequence of `reverse(A)` (because the recovered characters, read in A's order, form `reverse(s)`). So walk `reverse(A)` and at every character decide to *take* it (only if that character is still needed) or *skip* it. Whenever a complete candidate of the right length is formed, keep it if it's smaller than the best so far. **Why it's correct.** It literally enumerates every count-valid subsequence of `reverse(A)` and returns the minimum, so it cannot miss the answer. **Why it's hopeless at scale.** With `|A|` up to 10⁴, the take/skip tree has up to `2ⁿ` leaves. Even aggressive pruning (stop when a count is exhausted, abandon branches already larger than the best) leaves it exponential in the worst case. **Bridge to optimal.** The exponential search is really just trying to make each output position as small as possible while keeping the remaining counts satisfiable. A monotonic stack performs exactly that local decision greedily in a single pass — pop a larger committed character whenever enough copies remain to the left to re-collect it. Time complexity: O(2ⁿ). Space complexity: O(n).

Arrays & Hashing · 80 of 83 · 11 min

A string A was produced from a secret string s by the procedure A = merge(reverse(s), shuffle(s)), where:

reverse(s) reverses s,
shuffle(s) is some permutation of s,
merge(p, q) interleaves p and q preserving the internal order of each.

Given A, recover the lexicographically smallest possible s.

In plain English

Since reverse(s) and shuffle(s) are both rearrangements of s, A contains each character of s exactly twice — so s must use count[c]/2 of each character c. One of A's two interleaved halves is reverse(s). Reading the chosen subsequence in A's left-to-right order therefore gives reverse(s); equivalently, s itself is a subsequence of reverse(A). To minimise s lexicographically we pick the smallest such subsequence with the required counts, which a monotonic-stack greedy delivers in one backward pass over A.

Examples

Example 1

Input: A = "eggegg"
Output: egg
Note: Counts e:2, g:4 → need e:1, g:2. The lexicographically smallest s using one e and two g's that is recoverable is "egg".

Example 2

Input: A = "aabb"
Output: ba
Note: Need a:1, b:1. s must be a subsequence of reverse(A) = "bbaa"; the only order achievable is "ba" (a 'b' followed by an 'a'). Note "ab" is NOT valid here — this is why we scan A backwards.

Example 3

Input: A = "abab"
Output: ab
Note: Need a:1, b:1. reverse(A) = "baba"; greedily we can pop the leading 'b' (another 'b' remains) and emit "ab".

Constraints

1 ≤ |A| ≤ 10⁴ (|A| is even)
A consists of lowercase English letters only
Every character occurs an even number of times in A
Return the lexicographically smallest valid s

Clarifying questions4First question: How many of each character does s contain?Explore questions

Q1.How many of each character does s contain?
Exactly half of A's count for that character. Both reverse(s) and shuffle(s) contribute one copy each, so every character occurs an even number of times in A.
Q2.Why scan A from right to left?
s is a subsequence of reverse(A). Walking A backwards is walking reverse(A) forwards, so the stack we build comes out as s in the correct order — no final reversal needed.
Q3.When is it safe to pop a larger character off the stack?
Only when there are still enough copies of it to the left (unprocessed) to satisfy its required count later — i.e. need[top] - used[top] < remaining[top].
Q4.What's the alphabet?
Lowercase a–z, so counts, used, and remaining are 26-element arrays — O(1) space.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Given A = merge(reverse(s), shuffle(s)), each character of s appears twice in A, so s needs exactly count[c]/2 of each character c. The recovered s read in A-order is a subsequence of reverse(A); to get the lexicographically smallest s, scan A from RIGHT to LEFT and greedily build s with a monotonic stack: take a needed character, but first pop any larger characters already on the stack provided enough copies remain to the left to re-collect them later. O(n) time, O(1) space (26-letter counts).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can peel a scary 'reverse + shuffle + merge' wrapper down to 'smallest subsequence of reverse(A) with fixed per-character counts', and then implement the count-aware monotonic-stack greedy correctly.

Where candidates slip

Building s left-to-right (which yields the wrong order — try "aabb"), or popping a larger top without checking that enough copies remain to the left to re-collect it.

How to stand out

Derive the half-count fact, explain why scanning A right-to-left makes the stack equal s, and state the precise pop condition: discard a bigger top only when need[top] - used[top] < remaining[top].

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Search All Valid Subsequences	`O(2ⁿ)`	`O(n)`	Use it to establish what 'valid s' means and why the answer is a smallest subsequence, then note the search is exponential.	Read
2	Greedy Monotonic Stack over reverse(A) (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want — 'smallest count-valid subsequence of reverse(A) via a count-aware monotonic stack'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Peeling the construction down to a greedy

How to read it:The merge/shuffle/reverse wrapper reduces to: smallest subsequence of reverse(A) with half-counts.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Search All Valid Subsequences

TimeO(2ⁿ)SpaceO(n)

Use it to establish what 'valid s' means and why the answer is a smallest subsequence, then note the search is exponential.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What exactly makes a string s valid here? It must use need[c] copies of each character and be a subsequence of reverse(A).

2Hint 2Explore hint

Enumerate subsequences of reverse(A): at each position either take the character (if still needed) or skip it.

3Hint 3Explore hint

Keep the lexicographically smallest completed candidate. This explores up to 2ⁿ branches — correct but exponential.

A · Core idea

Make the validity condition explicit, then search. A valid s uses exactly need[c] = count[c]/2 of each character and must be a subsequence of reverse(A) (because the recovered characters, read in A's order, form reverse(s)). So walk reverse(A) and at every character decide to take it (only if that character is still needed) or skip it. Whenever a complete candidate of the right length is formed, keep it if it's smaller than the best so far.

Why it's correct. It literally enumerates every count-valid subsequence of reverse(A) and returns the minimum, so it cannot miss the answer.

Why it's hopeless at scale. With |A| up to 10⁴, the take/skip tree has up to 2ⁿ leaves. Even aggressive pruning (stop when a count is exhausted, abandon branches already larger than the best) leaves it exponential in the worst case.

Bridge to optimal. The exponential search is really just trying to make each output position as small as possible while keeping the remaining counts satisfiable. A monotonic stack performs exactly that local decision greedily in a single pass — pop a larger committed character whenever enough copies remain to the left to re-collect it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = "aabb"

Array state

take b

path = "b"

i ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final resultba

C · Code with teaching comments

Reference implementation previewpublic String reverseShuffleMerge(String s) { int[] count = new int[26]; for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++; int[] need = new int[26]; int target = 0;Explore the full code

solution.javaJava

Brute Force — Search All Valid Subsequences — reference

3 teaching notes

1
public String reverseShuffleMerge(String s) {
2
    int[] count = new int[26];
3
    for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;
4
    int[] need = new int[26];
5
    int target = 0;
6
    for (int i = 0; i < 26; i++) { need[i] = count[i] / 2; target += need[i]; }
7
    // s is a subsequence of reverse(A), so we search over rev.
8
    String rev = new StringBuilder(s).reverse().toString();
9
    String[] best = {null};
10
    dfs(rev, 0, new StringBuilder(), new int[26], need, target, best);
11
    return best[0];
12
}
13
 
14
private void dfs(String rev, int i, StringBuilder path, int[] used,
15
                 int[] need, int target, String[] best) {
16
    if (path.length() == target) {
17
        String cand = path.toString();
18
        if (best[0] == null || cand.compareTo(best[0]) < 0) best[0] = cand;
19
        return;
20
    }
21
    if (i == rev.length()) return;
22
    int c = rev.charAt(i) - 'a';
23
    // Only take a character while it is still required.
24
    if (used[c] < need[c]) {
25
        used[c]++; path.append(rev.charAt(i));
26
        dfs(rev, i + 1, path, used, need, target, best);
27
        path.deleteCharAt(path.length() - 1); used[c]--;
28
    }
29
    dfs(rev, i + 1, path, used, need, target, best);
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

The brute force makes the validity rule precise — s uses half-counts and is a subsequence of reverse(A). Once you see the answer is 'smallest count-valid subsequence', the greedy stack is the standard O(n) realisation of that exact goal.

ComplexityO(2ⁿ) time, O(n) space — Each of the n positions of reverse(A) is taken or skipped, giving up to 2ⁿ branches; each completed candidate costs O(n) to compare. Exponential time, O(n) recursion depth.

E · Edge cases and pitfalls3Searching subsequences of A instead of reverse(A) — yields reverse(s), not s.Explore edge cases

Pitfalls

Searching subsequences of A instead of reverse(A) — yields reverse(s), not s.
Forgetting the per-character need cap, producing wrong-multiset candidates.
Expecting it to finish for large A — it is exponential.

03.2

Approach 2 of 2 · Optimal

Greedy Monotonic Stack over reverse(A) (Optimal)

TimeO(n)SpaceO(1)

The answer they want — 'smallest count-valid subsequence of reverse(A) via a count-aware monotonic stack'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You want each output character as small as possible, as early as possible, while keeping the remaining counts satisfiable. What structure supports 'undo a committed bigger choice'?

2Hint 2Explore hint

Scan A right-to-left. Track need[c], used[c] (on the stack) and remaining[c] (still to the left). Only take a character while used[c] < need[c].

3Hint 3Explore hint

Before pushing c, pop any stack-top larger than c — but only if you can still re-collect it later: need[top] - used[top] < remaining[top]. Then push c.

A · Core idea

Scan A from right to left (i.e. left-to-right over reverse(A)), building s on a stack. Maintain three 26-slot arrays: need[c] = count[c]/2, used[c] (how many c's are currently on the stack), and remaining[c] (how many c's are still unprocessed, to the left).

Per character `c` (after decrementing `remaining[c]`):

If used[c] == need[c], we already have all the c's we need — skip it (taking more would exceed the multiset).
Otherwise, before pushing, pop any stack-top t that is larger than c provided need[t] - used[t] < remaining[t]. That condition means: even after removing this t from the stack, enough t's remain to the left to re-collect later and still meet need[t]. Popping a larger character that sits before c makes the result lexicographically smaller.
Then push c and increment used[c].

Why right-to-left. The recovered characters, read in A's natural order, spell reverse(s). Reading A backwards is reading reverse(A) forwards, so the stack we accumulate spells s directly — no final reversal. The "aabb" → "ba" case is the proof: a left-to-right greedy would wrongly emit "ab".

Why the pop guard is exactly `need[t] - used[t] < remaining[t]`. When we consider popping t, used[t] still counts the copy we're about to remove. After removal we'd need need[t] - (used[t]-1) more t's, which must be available among the remaining[t] unprocessed copies: remaining[t] >= need[t] - used[t] + 1, i.e. need[t] - used[t] < remaining[t]. If that fails, this t is irreplaceable — keep it and stop popping.

Why each character is pushed/popped at most once gives the linear bound — the inner while-loop is amortised O(1).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = "eggegg"

Array state

after g, g

stack = [g, g]

[0]

[1]

Current pointerResolved stateNot processed

Final resultegg

C · Code with teaching comments

solution.javaJava

Greedy Monotonic Stack over reverse(A) (Optimal) — optimal

5 teaching notes

1
public String reverseShuffleMerge(String s) {
2
    int[] count = new int[26];
3
    for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;
4
    int[] need = new int[26];
5
    // s uses exactly half of each character's total count.
6
    for (int i = 0; i < 26; i++) need[i] = count[i] / 2;
7
    int[] remaining = count.clone();
8
    int[] used = new int[26];
9
    StringBuilder stack = new StringBuilder();
10
    // Right-to-left scan = forward over reverse(A), so the stack spells s directly.
11
    for (int i = s.length() - 1; i >= 0; i--) {
12
        int c = s.charAt(i) - 'a';
13
        remaining[c]--;
14
        // Already have enough c's — taking more would break the required multiset.
15
        if (used[c] >= need[c]) continue;
16
        while (stack.length() > 0) {
17
            int top = stack.charAt(stack.length() - 1) - 'a';
18
            // Pop a larger top only if enough copies remain left to re-collect it
19
            // later.
20
            if (top > c && need[top] - used[top] < remaining[top]) {
21
                stack.deleteCharAt(stack.length() - 1);
22
                used[top]--;
23
            } else {
24
                break;
25
            }
26
        }
27
        // Commit c to the result and bump used[c].
28
        stack.append((char) (c + 'a'));
29
        used[c]++;
30
    }
31
    return stack.toString();
32
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.32 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

This is the count-constrained cousin of 'remove k digits to make the smallest number'. The standard monotonic stack greedily discards a larger earlier character whenever something smaller arrives — here the extra twist is a feasibility guard (enough copies remain) and a take-cap (don't exceed need[c]). Scanning the reversed string is the move that makes the stack come out as s.

ComplexityO(n) time, O(1) space — Each character is pushed and popped at most once across the single backward pass → O(n) total. The counts, used, and remaining arrays are 26 entries regardless of n → O(1) space.

E · Edge cases and pitfalls8A = "aabb" — reverse(A)="bbaa". Take b; at 'a', b>a but remaining b is 0 so need-used(0) < 0 is false → can't pop → push a → "ba". Shows why the pop guard matters.Explore edge cases

Edge cases handled

A = "aabb"reverse(A)="bbaa". Take b; at 'a', b>a but remaining b is 0 so need-used(0) < 0 is false → can't pop → push a → "ba". Shows why the pop guard matters.
A = "abab"reverse="baba". Take b; at 'a', another b remains so pop b, push a; later push b → "ab".
A = "aa"need a:1 → single character → "a".
A = "eggegg"Classic case → "egg" (pops both g's when the e arrives).

Pitfalls

Scanning A left-to-right instead of right-to-left — produces the wrong order (fails "aabb").
Popping a larger top without the remaining-copies guard — can leave a character's quota unfillable.
Decrementing remaining at the wrong time — it must drop the moment the character is read.
Taking a character past its need quota, corrupting the multiset.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic String reverseShuffleMerge(String s) { int[] count = new int[26]; for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++; int[] need = new int[26]; for (int i = 0; i < 26; i++) need[i] = count[i] / 2;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Scanning in the wrong direction

s is a subsequence of reverse(A). Scanning A forward builds reverse(s); "aabb" would wrongly produce "ab" instead of the correct "ba".

Explore the code comparison

Don't write this

for ch in s:  # forward over A — wrong order
    ...

Write this instead

for ch in reversed(s):  # forward over reverse(A) — stack spells s
    ...

Popping without the feasibility guard

Discarding a larger top is only safe if enough of that character remains to the left to satisfy its need later; otherwise its quota becomes impossible to fill.

Explore the code comparison

Don't write this

while stack and stack[-1] > ch:
    used[stack[-1]] -= 1
    stack.pop()

Write this instead

while stack and stack[-1] > ch and need[stack[-1]] - used[stack[-1]] < remaining[stack[-1]]:
    used[stack[-1]] -= 1
    stack.pop()

Exceeding the required count

s contains exactly count[c]/2 of each character. Taking more than need[c] corrupts the multiset and the answer length.

Explore the code comparison

Don't write this

// always take the character
stack.append((char) (c + 'a'));
used[c]++;

Write this instead

if (used[c] >= need[c]) continue;
stack.append((char) (c + 'a'));
used[c]++;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy smallest subsequence with required counts (scan reversed, monotonic stack)

Code pattern to memorize

need[c] = count(A, c) // 2
scan A right-to-left:
  remaining[c] -= 1
  if used[c] < need[c]:
    while stack and stack[-1] > c and need[top]-used[top] < remaining[top]:
        used[top] -= 1; stack.pop()
    stack.push(c); used[c] += 1
return stack joined

Rules to remember

1Each character appears an even number of times in A; s uses exactly half of each.
2Scan A right-to-left — that makes the stack you build equal to s directly (it walks reverse(A)).
3Only take a character while you still need it: used[c] < need[c].
4Pop a larger stack-top only if enough of it remains to the left to re-collect later: need[top] - used[top] < remaining[top].
5Decrement remaining[c] the instant you read c, before deciding to take or pop.

Use this pattern when

Recover the lexicographically smallest string under a merge/shuffle/reverse construction
Build the smallest subsequence that uses an exact multiset of characters
Greedy 'remove bigger earlier characters if you can afford to' with a stack
Counts are fixed and the alphabet is small (a–z)

Choose another pattern when

No required-count constraint, just smallest k-length subsequence → classic 'remove k digits' stack
Largest (not smallest) result wanted → flip the comparison and pop smaller tops
Characters must keep relative positions exactly → not a free greedy, likely DP
You need ALL valid s, not just the smallest → enumerate, don't greedily prune

Interview takeaway

Strip the construction down to its invariant: s is the smallest subsequence of reverse(A) using half of each character. Scanning A backwards turns the build into a standard monotonic-stack greedy, where a larger top is discarded only when leftover copies guarantee you can rebuild it.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCount-constrained smallest-subsequence via a monotonic stack. When you must build the lexicographically smallest string using a fixed multiset of characters, greedily push characters and pop larger committed ones whenever enough copies remain to re-collect them. The construction-specific twist here is recognising s is a subsequence of reverse(A), so you scan A backwards.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Remove K Digits
Coming soon
The base monotonic-stack greedy for the smallest number — no per-character count cap.
Remove Duplicate Letters
Coming soon
Smallest subsequence with each letter once — same 'pop if it reappears later' guard.
Smallest Subsequence of Distinct Characters
Coming soon
Duplicate of Remove Duplicate Letters — identical greedy stack.
Create Maximum Number
Coming soon
Monotonic stack to pick the best subsequence, then merge — a harder cousin.

Same pattern

←

Colorful Number

Continue · Next problem

Sherlock and the Valid String

hardStrings0Sometimes asked

Reverse Shuffle Merge

Arrays & Hashing · 80 of 83 · 11 min

A string A was produced from a secret string s by the procedure A = merge(reverse(s), shuffle(s)), where:

reverse(s) reverses s,
shuffle(s) is some permutation of s,
merge(p, q) interleaves p and q preserving the internal order of each.

Given A, recover the lexicographically smallest possible s.

In plain English

Examples

Example 1

Input: A = "eggegg"
Output: egg
Note: Counts e:2, g:4 → need e:1, g:2. The lexicographically smallest s using one e and two g's that is recoverable is "egg".

Example 2

Input: A = "aabb"
Output: ba
Note: Need a:1, b:1. s must be a subsequence of reverse(A) = "bbaa"; the only order achievable is "ba" (a 'b' followed by an 'a'). Note "ab" is NOT valid here — this is why we scan A backwards.

Example 3

Input: A = "abab"
Output: ab
Note: Need a:1, b:1. reverse(A) = "baba"; greedily we can pop the leading 'b' (another 'b' remains) and emit "ab".

Constraints

1 ≤ |A| ≤ 10⁴ (|A| is even)
A consists of lowercase English letters only
Every character occurs an even number of times in A
Return the lexicographically smallest valid s

Clarifying questions4First question: How many of each character does s contain?Explore questions

Q1.How many of each character does s contain?
Exactly half of A's count for that character. Both reverse(s) and shuffle(s) contribute one copy each, so every character occurs an even number of times in A.
Q2.Why scan A from right to left?
s is a subsequence of reverse(A). Walking A backwards is walking reverse(A) forwards, so the stack we build comes out as s in the correct order — no final reversal needed.
Q3.When is it safe to pop a larger character off the stack?
Only when there are still enough copies of it to the left (unprocessed) to satisfy its required count later — i.e. need[top] - used[top] < remaining[top].
Q4.What's the alphabet?
Lowercase a–z, so counts, used, and remaining are 26-element arrays — O(1) space.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Building s left-to-right (which yields the wrong order — try "aabb"), or popping a larger top without checking that enough copies remain to the left to re-collect it.

How to stand out

Derive the half-count fact, explain why scanning A right-to-left makes the stack equal s, and state the precise pop condition: discard a bigger top only when need[top] - used[top] < remaining[top].

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Search All Valid Subsequences	`O(2ⁿ)`	`O(n)`	Use it to establish what 'valid s' means and why the answer is a smallest subsequence, then note the search is exponential.	Read
2	Greedy Monotonic Stack over reverse(A) (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want — 'smallest count-valid subsequence of reverse(A) via a count-aware monotonic stack'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Peeling the construction down to a greedy

How to read it:The merge/shuffle/reverse wrapper reduces to: smallest subsequence of reverse(A) with half-counts.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Search All Valid Subsequences

TimeO(2ⁿ)SpaceO(n)

Use it to establish what 'valid s' means and why the answer is a smallest subsequence, then note the search is exponential.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What exactly makes a string s valid here? It must use need[c] copies of each character and be a subsequence of reverse(A).

2Hint 2Explore hint

Enumerate subsequences of reverse(A): at each position either take the character (if still needed) or skip it.

3Hint 3Explore hint

Keep the lexicographically smallest completed candidate. This explores up to 2ⁿ branches — correct but exponential.

A · Core idea

Why it's correct. It literally enumerates every count-valid subsequence of reverse(A) and returns the minimum, so it cannot miss the answer.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = "aabb"

Array state

take b

path = "b"

i ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final resultba

C · Code with teaching comments

solution.javaJava

Brute Force — Search All Valid Subsequences — reference

3 teaching notes

1
public String reverseShuffleMerge(String s) {
2
    int[] count = new int[26];
3
    for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;
4
    int[] need = new int[26];
5
    int target = 0;
6
    for (int i = 0; i < 26; i++) { need[i] = count[i] / 2; target += need[i]; }
7
    // s is a subsequence of reverse(A), so we search over rev.
8
    String rev = new StringBuilder(s).reverse().toString();
9
    String[] best = {null};
10
    dfs(rev, 0, new StringBuilder(), new int[26], need, target, best);
11
    return best[0];
12
}
13
 
14
private void dfs(String rev, int i, StringBuilder path, int[] used,
15
                 int[] need, int target, String[] best) {
16
    if (path.length() == target) {
17
        String cand = path.toString();
18
        if (best[0] == null || cand.compareTo(best[0]) < 0) best[0] = cand;
19
        return;
20
    }
21
    if (i == rev.length()) return;
22
    int c = rev.charAt(i) - 'a';
23
    // Only take a character while it is still required.
24
    if (used[c] < need[c]) {
25
        used[c]++; path.append(rev.charAt(i));
26
        dfs(rev, i + 1, path, used, need, target, best);
27
        path.deleteCharAt(path.length() - 1); used[c]--;
28
    }
29
    dfs(rev, i + 1, path, used, need, target, best);
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Searching subsequences of A instead of reverse(A) — yields reverse(s), not s.Explore edge cases

Pitfalls

Searching subsequences of A instead of reverse(A) — yields reverse(s), not s.
Forgetting the per-character need cap, producing wrong-multiset candidates.
Expecting it to finish for large A — it is exponential.

03.2

Approach 2 of 2 · Optimal

Greedy Monotonic Stack over reverse(A) (Optimal)

TimeO(n)SpaceO(1)

The answer they want — 'smallest count-valid subsequence of reverse(A) via a count-aware monotonic stack'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You want each output character as small as possible, as early as possible, while keeping the remaining counts satisfiable. What structure supports 'undo a committed bigger choice'?

2Hint 2Explore hint

Scan A right-to-left. Track need[c], used[c] (on the stack) and remaining[c] (still to the left). Only take a character while used[c] < need[c].

3Hint 3Explore hint

Before pushing c, pop any stack-top larger than c — but only if you can still re-collect it later: need[top] - used[top] < remaining[top]. Then push c.

A · Core idea

Per character `c` (after decrementing `remaining[c]`):

If used[c] == need[c], we already have all the c's we need — skip it (taking more would exceed the multiset).
Otherwise, before pushing, pop any stack-top t that is larger than c provided need[t] - used[t] < remaining[t]. That condition means: even after removing this t from the stack, enough t's remain to the left to re-collect later and still meet need[t]. Popping a larger character that sits before c makes the result lexicographically smaller.
Then push c and increment used[c].

Why each character is pushed/popped at most once gives the linear bound — the inner while-loop is amortised O(1).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = "eggegg"

Array state

after g, g

stack = [g, g]

[0]

[1]

Current pointerResolved stateNot processed

Final resultegg

C · Code with teaching comments

solution.javaJava

Greedy Monotonic Stack over reverse(A) (Optimal) — optimal

5 teaching notes

1
public String reverseShuffleMerge(String s) {
2
    int[] count = new int[26];
3
    for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;
4
    int[] need = new int[26];
5
    // s uses exactly half of each character's total count.
6
    for (int i = 0; i < 26; i++) need[i] = count[i] / 2;
7
    int[] remaining = count.clone();
8
    int[] used = new int[26];
9
    StringBuilder stack = new StringBuilder();
10
    // Right-to-left scan = forward over reverse(A), so the stack spells s directly.
11
    for (int i = s.length() - 1; i >= 0; i--) {
12
        int c = s.charAt(i) - 'a';
13
        remaining[c]--;
14
        // Already have enough c's — taking more would break the required multiset.
15
        if (used[c] >= need[c]) continue;
16
        while (stack.length() > 0) {
17
            int top = stack.charAt(stack.length() - 1) - 'a';
18
            // Pop a larger top only if enough copies remain left to re-collect it
19
            // later.
20
            if (top > c && need[top] - used[top] < remaining[top]) {
21
                stack.deleteCharAt(stack.length() - 1);
22
                used[top]--;
23
            } else {
24
                break;
25
            }
26
        }
27
        // Commit c to the result and bump used[c].
28
        stack.append((char) (c + 'a'));
29
        used[c]++;
30
    }
31
    return stack.toString();
32
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.32 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Edge cases handled

A = "aabb"reverse(A)="bbaa". Take b; at 'a', b>a but remaining b is 0 so need-used(0) < 0 is false → can't pop → push a → "ba". Shows why the pop guard matters.
A = "abab"reverse="baba". Take b; at 'a', another b remains so pop b, push a; later push b → "ab".
A = "aa"need a:1 → single character → "a".
A = "eggegg"Classic case → "egg" (pops both g's when the e arrives).

Pitfalls

Scanning A left-to-right instead of right-to-left — produces the wrong order (fails "aabb").
Popping a larger top without the remaining-copies guard — can leave a character's quota unfillable.
Decrementing remaining at the wrong time — it must drop the moment the character is read.
Taking a character past its need quota, corrupting the multiset.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Scanning in the wrong direction

s is a subsequence of reverse(A). Scanning A forward builds reverse(s); "aabb" would wrongly produce "ab" instead of the correct "ba".

Explore the code comparison

Don't write this

for ch in s:  # forward over A — wrong order
    ...

Write this instead

for ch in reversed(s):  # forward over reverse(A) — stack spells s
    ...

Popping without the feasibility guard

Discarding a larger top is only safe if enough of that character remains to the left to satisfy its need later; otherwise its quota becomes impossible to fill.

Explore the code comparison

Don't write this

while stack and stack[-1] > ch:
    used[stack[-1]] -= 1
    stack.pop()

Write this instead

while stack and stack[-1] > ch and need[stack[-1]] - used[stack[-1]] < remaining[stack[-1]]:
    used[stack[-1]] -= 1
    stack.pop()

Exceeding the required count

s contains exactly count[c]/2 of each character. Taking more than need[c] corrupts the multiset and the answer length.

Explore the code comparison

Don't write this

// always take the character
stack.append((char) (c + 'a'));
used[c]++;

Write this instead

if (used[c] >= need[c]) continue;
stack.append((char) (c + 'a'));
used[c]++;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy smallest subsequence with required counts (scan reversed, monotonic stack)

Code pattern to memorize

need[c] = count(A, c) // 2
scan A right-to-left:
  remaining[c] -= 1
  if used[c] < need[c]:
    while stack and stack[-1] > c and need[top]-used[top] < remaining[top]:
        used[top] -= 1; stack.pop()
    stack.push(c); used[c] += 1
return stack joined

Rules to remember

1Each character appears an even number of times in A; s uses exactly half of each.
2Scan A right-to-left — that makes the stack you build equal to s directly (it walks reverse(A)).
3Only take a character while you still need it: used[c] < need[c].
4Pop a larger stack-top only if enough of it remains to the left to re-collect later: need[top] - used[top] < remaining[top].
5Decrement remaining[c] the instant you read c, before deciding to take or pop.

Use this pattern when

Recover the lexicographically smallest string under a merge/shuffle/reverse construction
Build the smallest subsequence that uses an exact multiset of characters
Greedy 'remove bigger earlier characters if you can afford to' with a stack
Counts are fixed and the alphabet is small (a–z)

Choose another pattern when

No required-count constraint, just smallest k-length subsequence → classic 'remove k digits' stack
Largest (not smallest) result wanted → flip the comparison and pop smaller tops
Characters must keep relative positions exactly → not a free greedy, likely DP
You need ALL valid s, not just the smallest → enumerate, don't greedily prune

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Remove K Digits
Coming soon
The base monotonic-stack greedy for the smallest number — no per-character count cap.
Remove Duplicate Letters
Coming soon
Smallest subsequence with each letter once — same 'pop if it reappears later' guard.
Smallest Subsequence of Distinct Characters
Coming soon
Duplicate of Remove Duplicate Letters — identical greedy stack.
Create Maximum Number
Coming soon
Monotonic stack to pick the best subsequence, then merge — a harder cousin.

Same pattern

←

Colorful Number

Continue · Next problem

Sherlock and the Valid String