Loading…

mediumDynamic ProgrammingSometimes asked

Abbreviation

Q: How do you solve Abbreviation using the Brute Force — Recurse on Capitalize / Delete approach?

When to use it: State it first to reveal the two branches and the overlapping subproblems, then add memoization or a table. The most literal reading: try to consume `b` one character at a time while scanning `a`. Maintain two indices, `i` into `a` and `j` into `b`. **The branches.** If `a[i]` is lowercase, you have a genuine choice. You may *capitalize* it — but only if `toUpper(a[i]) == b[j]` — which consumes `b[j]` and advances both pointers. Or you may *delete* it, advancing only `i`. If `a[i]` is uppercase, there is no choice: it must equal `b[j]` (advance both); if it doesn't, this path is impossible. **Why it must branch (greedy fails).** Consider `a = "Aa", b = "A"`. Greedily capitalizing the lowercase 'a' would over-produce; you must *delete* it instead. Conversely sometimes you must capitalize even though deleting looks simpler. Because a lowercase letter that *could* match might need to be deleted to let a later letter match, you cannot commit greedily — you explore both forks. **Base cases.** When `j == m` (all of `b` produced), success requires every remaining character of `a` to be lowercase (so they can be deleted); a leftover uppercase letter forces failure. When `i == n` but `j < m`, you've run out of letters to supply `b` → failure. **Why we don't ship this.** Every lowercase letter doubles the path count, so the tree is `2ⁿ`. But the only thing that distinguishes a subproblem is the pair `(i, j)`, and there are just `n·m` such pairs — the same states are recomputed exponentially often. That redundancy is the cue to memoize. Time complexity: O(2ⁿ). Space complexity: O(n).

Q: How do you solve Abbreviation using the 2D Boolean DP — Tabulation (Optimal) approach?

When to use it: The answer they want. Phrase it as 'an edit-distance-style grid where each cell is reachable-or-not'. Turn the recursion inside-out. Let `dp[i][j]` mean *'the first `i` characters of `a` can be transformed into the first `j` characters of `b`'*. The answer is `dp[n][m]`. **Initialization.** `dp[0][0] = true` — an empty prefix of `a` trivially yields an empty prefix of `b`. The first column `dp[i][0]` asks 'can `a[0..i-1]` be deleted entirely?'. That's true only if every one of those characters is lowercase, so `dp[i][0] = dp[i-1][0] && isLowercase(a[i-1])`. The first row `dp[0][j>0]` is false: nothing can produce a non-empty `b`. **Transition — uppercase a[i-1].** A frozen letter can only be kept, and only if it equals the target: `dp[i][j] = (a[i-1] == b[j-1]) && dp[i-1][j-1]`. If they differ, the cell is false. **Transition — lowercase a[i-1].** Two ways to reach `dp[i][j]`: - *Delete* `a[i-1]`: the target prefix is unchanged, so inherit `dp[i-1][j]`. - *Capitalize* `a[i-1]` to consume `b[j-1]`: legal only when `toUpper(a[i-1]) == b[j-1]`, contributing `dp[i-1][j-1]`. Combine with OR: `dp[i][j] = dp[i-1][j] || (toUpper(a[i-1]) == b[j-1] && dp[i-1][j-1])`. **Why iterate j from 0.** The `j == 0` column carries the 'delete everything so far' state. If you start `j` at 1 you lose the ability to delete a prefix of `a` before the first `b` character is matched — and `a = "xY", b = "Y"` would wrongly fail. **Why this is correct and fast.** Every (i, j) state is computed exactly once from already-filled neighbours above and to the upper-left, so there's no recomputation. `n·m ≤ 10⁶` cells for the constraints — instant. Time complexity: O(n·m). Space complexity: O(n·m).

Q: How do you solve Abbreviation using the Rolling-Row DP — O(m) Space approach?

When to use it: Mention after the 2D table as the memory-tightening step when |a| can be large. The tabulation only ever reads the immediately previous row, so storing all `n+1` rows is wasteful. Keep `prev` (row `i-1`) and `cur` (row `i`). **Handling column 0 per row.** `cur[0]` answers 'can `a[0..i-1]` be entirely deleted?', which is `prev[0] && isLowercase(a[i-1])`. Set this before the inner loop because the lowercase delete branch reads `cur`'s own column-0 lineage indirectly through `prev`. **The inner loop** is identical to the 2D version with `dp[i-1][j] → prev[j]` and `dp[i-1][j-1] → prev[j-1]`. After finishing the row, swap `prev` and `cur` (and clear `cur`). **Why ship it when |a| is large.** With `|a|, |b| ≤ 1000` the full table is only ~10⁶ booleans — fine. But the O(m) version generalises better and demonstrates you see the bounded look-back. The trade-off: you lose the full table, so you can't reconstruct *which* letters were capitalised vs deleted without extra bookkeeping. Time complexity: O(n·m). Space complexity: O(m).

Dynamic Programming · 31 of 44 · 12 min

You are given two strings, a and b. You can perform the following operations on string a:

1
Capitalize zero or more of a's lowercase letters.
2
Delete all of the remaining lowercase letters in a.

Given a and b, determine whether it is possible to make a equal to b using these operations. Note that b consists only of uppercase letters, and the uppercase letters already present in a can be neither deleted nor altered.

Return "YES" if a can be transformed into b, otherwise "NO".

In plain English

Think of walking through `a` once. Each lowercase letter offers a fork: capitalize it (and it must then equal the next needed letter of `b`) or throw it away. Each uppercase letter is fixed — it has to be the next needed letter of `b`, or the attempt is doomed. The question is whether some sequence of these forced and free choices reproduces `b` exactly.

Examples

Example 1

Input: a = "daBcd", b = "ABC"
Output: YES
Note: Delete the first 'd', capitalize 'a'→'A', keep 'B', capitalize 'c'→'C', delete the last 'd'. Result: "ABC".

Example 2

Input: a = "AbcDE", b = "AFDE"
Output: NO
Note: After keeping 'A', the next needed letter is 'F'. The only lowercase letters available are 'b' and 'c', which capitalize to 'B'/'C', never 'F'. No way to produce 'F'.

Example 3

Input: a = "AbcDE", b = "ABDE"
Output: YES
Note: Keep 'A', capitalize 'b'→'B', delete 'c', keep 'D', keep 'E'. Result: "ABDE".

Constraints

1 ≤ |a|, |b| ≤ 1000
`a` consists of uppercase and lowercase English letters
`b` consists only of uppercase English letters
Uppercase letters in `a` cannot be deleted or changed
Lowercase letters in `a` may each be capitalized or deleted

Clarifying questions4First question: Is `b` guaranteed to be all uppercase?Explore questions

Q1.Is `b` guaranteed to be all uppercase?
Yes. That's why every `b` character must come from a kept-uppercase or a capitalized-lowercase letter of `a`.
Q2.Can I delete uppercase letters in `a` that don't appear in `b`?
No — uppercase letters are frozen. A leftover uppercase letter in `a` with nothing to match in `b` immediately forces 'NO'.
Q3.Must lowercase letters that happen to match `b` be capitalized?
No, and that's the trap. A lowercase letter may need to be *deleted* even when capitalizing it would match, so a later letter can line up. That non-greedy choice is exactly what the DP explores.
Q4.What if |a| < |b|?
Then it's impossible — you can never produce more target characters than `a` has letters to supply. The DP returns false naturally, but you can short-circuit.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Decide whether string `a` can be turned into the all-uppercase string `b` using only two moves: capitalize zero or more lowercase letters of `a`, and delete the remaining lowercase letters. Uppercase letters in `a` are frozen — they can neither be deleted nor changed. This is a two-sequence subsequence-matching DP: dp[i][j] = can the first i characters of a produce the first j characters of b. A lowercase a[i-1] may be deleted (carry dp[i-1][j]) or capitalized to match b[j-1] (take dp[i-1][j-1]); an uppercase a[i-1] MUST match b[j-1] exactly. O(n·m) time and space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model an asymmetric transform (lowercase = delete-or-capitalize, uppercase = must-match) as a 2D boolean reachability DP rather than greedy character matching.

Where candidates slip

Trying to match greedily left-to-right (capitalize whenever it fits) — this fails because sometimes a lowercase letter that *could* match must instead be deleted so a later letter can match. Also forgetting that an unmatched uppercase letter in `a` makes the whole thing impossible.

How to stand out

Name it as a subsequence/edit-distance-style grid, derive the two branches from the case of the character, handle the j=0 column explicitly, then note the O(m)-space rolling-row optimization.

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 — Recurse on Capitalize / Delete	`O(2ⁿ)`	`O(n)`	State it first to reveal the two branches and the overlapping subproblems, then add memoization or a table.	Read
2	2D Boolean DP — Tabulation (Optimal)Optimal	`O(n·m)`	`O(n·m)`	The answer they want. Phrase it as 'an edit-distance-style grid where each cell is reachable-or-not'.	Read
3	Rolling-Row DP — O(m) Space	`O(n·m)`	`O(m)`	Mention after the 2D table as the memory-tightening step when \|a\| can be large.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewAt a[i-1]Uppercase?YesNo (lowercase)Explore the full tree

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 3

Brute Force — Recurse on Capitalize / Delete

TimeO(2ⁿ)SpaceO(n)

State it first to reveal the two branches and the overlapping subproblems, then add memoization or a table.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk a pointer i over `a` and j over `b`. At each step, what can you do with a[i] depending on whether it's upper or lowercase?

2Hint 2Explore hint

If a[i] is lowercase you branch: either capitalize it (only legal when it uppercases to b[j], then advance both) or delete it (advance i only). If a[i] is uppercase it must equal b[j] to advance both, else this path fails.

3Hint 3Explore hint

Base cases: if j reached the end of b, the rest of a must be all lowercase (deletable). If i reached the end of a but j hasn't, fail.

A · Core idea

The most literal reading: try to consume b one character at a time while scanning a. Maintain two indices, i into a and j into b.

The branches. If a[i] is lowercase, you have a genuine choice. You may capitalize it — but only if toUpper(a[i]) == b[j] — which consumes b[j] and advances both pointers. Or you may delete it, advancing only i. If a[i] is uppercase, there is no choice: it must equal b[j] (advance both); if it doesn't, this path is impossible.

Why it must branch (greedy fails). Consider a = "Aa", b = "A". Greedily capitalizing the lowercase 'a' would over-produce; you must delete it instead. Conversely sometimes you must capitalize even though deleting looks simpler. Because a lowercase letter that could match might need to be deleted to let a later letter match, you cannot commit greedily — you explore both forks.

Base cases. When j == m (all of b produced), success requires every remaining character of a to be lowercase (so they can be deleted); a leftover uppercase letter forces failure. When i == n but j < m, you've run out of letters to supply b → failure.

Why we don't ship this. Every lowercase letter doubles the path count, so the tree is 2ⁿ. But the only thing that distinguishes a subproblem is the pair (i, j), and there are just n·m such pairs — the same states are recomputed exponentially often. That redundancy is the cue to memoize.

B · Visual dry run

Interactive dry run

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

a = "aB", b = "B"

Interactive diagram

Recursion forks on every lowercase letter

f(0,0)

Active call / nodeSupporting contextReturned stateNot active

The same (i, j) state can be reached on multiple paths — the exponential waste.

Final resultYES

C · Code with teaching comments

Reference implementation previewpublic String abbreviation(String a, String b) { return solve(a, b, 0, 0) ? "YES" : "NO"; } private boolean solve(String a, String b, int i, int j) {Explore the full code

solution.javaJava

Brute Force — Recurse on Capitalize / Delete — reference

4 teaching notes

1
public String abbreviation(String a, String b) {
2
    return solve(a, b, 0, 0) ? "YES" : "NO";
3
}
4
 
5
private boolean solve(String a, String b, int i, int j) {
6
    // All of b produced — success only if every remaining char of a is lowercase
7
    // (deletable).
8
    if (j == b.length()) {
9
        for (int k = i; k < a.length(); k++) {
10
            if (Character.isUpperCase(a.charAt(k))) return false;
11
        }
12
        return true;
13
    }
14
    if (i == a.length()) return false;
15
    char ca = a.charAt(i);
16
    if (Character.isUpperCase(ca)) {
17
        // Uppercase a[i] is frozen: it MUST equal b[j], then both advance.
18
        return ca == b.charAt(j) && solve(a, b, i + 1, j + 1);
19
    }
20
    boolean capitalize = Character.toUpperCase(ca) == b.charAt(j)
21
            && solve(a, b, i + 1, j + 1);
22
    boolean delete = solve(a, b, i + 1, j);
23
    // Either fork succeeding is enough — this OR is why greedy can't replace the
24
    // recursion.
25
    return capitalize || delete;
26
}

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

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

There are only n·m distinct (i, j) states but exponentially many paths reach them. Caching each (i, j) the first time collapses 2ⁿ into n·m — the universal DP trigger of 'few states, recomputed often'.

ComplexityO(2ⁿ) time, O(n) space — Each lowercase character can branch two ways, giving up to 2ⁿ leaf paths; recursion depth is O(n) for the call stack.

E · Edge cases and pitfalls3Forgetting to verify leftover characters are lowercase when j hits the end of b.Explore edge cases

Pitfalls

Forgetting to verify leftover characters are lowercase when j hits the end of b.
Allowing the capitalize branch when toUpper(a[i]) != b[j] — an illegal move.
Running it on |a| = 1000 — 2ⁿ never returns; memoize or tabulate.

03.2

Approach 2 of 3 · Optimal

2D Boolean DP — Tabulation (Optimal)

TimeO(n·m)SpaceO(n·m)

The answer they want. Phrase it as 'an edit-distance-style grid where each cell is reachable-or-not'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Define dp[i][j] = can the first i characters of a be transformed into the first j characters of b? You want dp[n][m].

2Hint 2Explore hint

dp[0][0] = true (empty produces empty). Fill the j=0 column: dp[i][0] is true only while a[0..i-1] is all lowercase (everything deletable).

3Hint 3Explore hint

Transition by the case of a[i-1]: uppercase forces dp[i][j] = (a[i-1]==b[j-1]) && dp[i-1][j-1]; lowercase allows delete (dp[i-1][j]) OR capitalize (dp[i-1][j-1] when upper(a[i-1])==b[j-1]).

A · Core idea

Turn the recursion inside-out. Let dp[i][j] mean 'the first `i` characters of `a` can be transformed into the first `j` characters of `b`'. The answer is dp[n][m].

Initialization. dp[0][0] = true — an empty prefix of a trivially yields an empty prefix of b. The first column dp[i][0] asks 'can a[0..i-1] be deleted entirely?'. That's true only if every one of those characters is lowercase, so dp[i][0] = dp[i-1][0] && isLowercase(a[i-1]). The first row dp[0][j>0] is false: nothing can produce a non-empty b.

Transition — uppercase a[i-1]. A frozen letter can only be kept, and only if it equals the target: dp[i][j] = (a[i-1] == b[j-1]) && dp[i-1][j-1]. If they differ, the cell is false.

Transition — lowercase a[i-1]. Two ways to reach dp[i][j]:

Delete a[i-1]: the target prefix is unchanged, so inherit dp[i-1][j].
Capitalize a[i-1] to consume b[j-1]: legal only when toUpper(a[i-1]) == b[j-1], contributing dp[i-1][j-1].

Combine with OR: dp[i][j] = dp[i-1][j] || (toUpper(a[i-1]) == b[j-1] && dp[i-1][j-1]).

Why iterate j from 0. The j == 0 column carries the 'delete everything so far' state. If you start j at 1 you lose the ability to delete a prefix of a before the first b character is matched — and a = "xY", b = "Y" would wrongly fail.

Why this is correct and fast. Every (i, j) state is computed exactly once from already-filled neighbours above and to the upper-left, so there's no recomputation. n·m ≤ 10⁶ cells for the constraints — instant.

B · Visual dry run

Interactive dry run

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

a = "daBcd", b = "ABC"

Moves through the DP grid

How to read it:Delete steps down a row; capitalize/match steps diagonally consuming a b character.

Rendering diagram…

Final resultYES

C · Code with teaching comments

solution.javaJava

2D Boolean DP — Tabulation (Optimal) — optimal

5 teaching notes

1
public String abbreviation(String a, String b) {
2
    int n = a.length(), m = b.length();
3
    boolean[][] dp = new boolean[n + 1][m + 1];
4
    // Empty a produces empty b — the seed every path traces back to.
5
    dp[0][0] = true;
6
    for (int i = 1; i <= n; i++) {
7
        char ca = a.charAt(i - 1);
8
        for (int j = 0; j <= m; j++) {
9
            // Frozen letter: only the forced-match move is available.
10
            if (Character.isUpperCase(ca)) {
11
                if (j > 0 && ca == b.charAt(j - 1)) {
12
                    // Uppercase matches b[j-1] → reachable iff the smaller prefix was.
13
                    dp[i][j] = dp[i - 1][j - 1];
14
                }
15
            } else {
16
                // Lowercase delete: drop a[i-1], target prefix unchanged.
17
                dp[i][j] = dp[i - 1][j];
18
                if (j > 0 && Character.toUpperCase(ca) == b.charAt(j - 1)) {
19
                    // OR in the capitalize move when the uppercased letter equals
20
                    // b[j-1].
21
                    dp[i][j] = dp[i][j] || dp[i - 1][j - 1];
22
                }
23
            }
24
        }
25
    }
26
    return dp[n][m] ? "YES" : "NO";
27
}

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

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

The grid is identical in shape to Edit Distance and LCS; only the cell semantics change from 'cost' to 'reachable'. Recognising that lets you reuse the same loop skeleton and just swap the recurrence body — case-of-character decides the move set.

ComplexityO(n·m) time, O(n·m) space — Exactly (n+1)(m+1) cells, each filled in O(1) → O(n·m) time. The full table is O(n·m) space.

E · Edge cases and pitfalls7a = "Pi", b = "P" — Keep 'P', delete lowercase 'i' → dp[2][1] inherits dp[1][1]=T → YES.Explore edge cases

Edge cases handled

a = "Pi", b = "P"Keep 'P', delete lowercase 'i' → dp[2][1] inherits dp[1][1]=T → YES.
a = "a", b = "A"Capitalize 'a'→'A': dp[1][1] from dp[0][0]=T → YES.
a = "AB", b = "ABC"Only 2 frozen letters, need 3 targets; dp[2][3] stays false → NO.
a = "Ab", b = "AB" then trailing 'C'An uppercase letter with no matching b position keeps its column false → NO when unmatched.

Pitfalls

Starting the j loop at 1 — loses the delete-the-prefix state in column 0.
Comparing a[i-1] == b[j-1] in the lowercase branch instead of toUpper(a[i-1]) == b[j-1].
Forgetting that an uppercase letter that doesn't match simply leaves the cell false (never OR-in a delete for it).

03.3

Approach 3 of 3

Rolling-Row DP — O(m) Space

TimeO(n·m)SpaceO(m)

Mention after the 2D table as the memory-tightening step when |a| can be large.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

dp[i][*] depends only on dp[i-1][*]. Do you ever read a row older than the previous one?

2Hint 2Explore hint

Keep two 1D arrays, prev and cur, of length m+1. Compute cur from prev each row, then swap.

3Hint 3Explore hint

Watch the j=0 cell of cur: it must encode 'a[0..i-1] all lowercase', so set it before the inner loop based on prev[0] and the case of a[i-1].

A · Core idea

The tabulation only ever reads the immediately previous row, so storing all n+1 rows is wasteful. Keep prev (row i-1) and cur (row i).

Handling column 0 per row. cur[0] answers 'can a[0..i-1] be entirely deleted?', which is prev[0] && isLowercase(a[i-1]). Set this before the inner loop because the lowercase delete branch reads cur's own column-0 lineage indirectly through prev.

The inner loop is identical to the 2D version with dp[i-1][j] → prev[j] and dp[i-1][j-1] → prev[j-1]. After finishing the row, swap prev and cur (and clear cur).

Why ship it when |a| is large. With |a|, |b| ≤ 1000 the full table is only ~10⁶ booleans — fine. But the O(m) version generalises better and demonstrates you see the bounded look-back. The trade-off: you lose the full table, so you can't reconstruct which letters were capitalised vs deleted without extra bookkeeping.

B · Visual dry run

Interactive dry run

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

a = "AbcDE", b = "ABDE"

Two rows leapfrogging down the grid

How to read it:Only prev and cur exist at any time; cur becomes prev each iteration.

Rendering diagram…

Final resultYES

C · Code with teaching comments

Reference implementation previewpublic String abbreviation(String a, String b) { int n = a.length(), m = b.length(); boolean[] prev = new boolean[m + 1]; prev[0] = true; for (int i = 1; i <= n; i++) {Explore the full code

solution.javaJava

Rolling-Row DP — O(m) Space — reference

4 teaching notes

1
public String abbreviation(String a, String b) {
2
    int n = a.length(), m = b.length();
3
    boolean[] prev = new boolean[m + 1];
4
    // Row 0, column 0: empty a yields empty b.
5
    prev[0] = true;
6
    for (int i = 1; i <= n; i++) {
7
        char ca = a.charAt(i - 1);
8
        boolean[] cur = new boolean[m + 1];
9
        // Can a[0..i-1] still be fully deleted? Only if it was before AND this char is
10
        // lowercase.
11
        cur[0] = prev[0] && Character.isLowerCase(ca);
12
        for (int j = 1; j <= m; j++) {
13
            if (Character.isUpperCase(ca)) {
14
                // Uppercase forced match reads the diagonal from the previous row.
15
                if (ca == b.charAt(j - 1)) cur[j] = prev[j - 1];
16
            } else {
17
                cur[j] = prev[j];
18
                if (Character.toUpperCase(ca) == b.charAt(j - 1)) {
19
                    cur[j] = cur[j] || prev[j - 1];
20
                }
21
            }
22
        }
23
        // Slide the window: this row becomes the previous row for the next iteration.
24
        prev = cur;
25
    }
26
    return prev[m] ? "YES" : "NO";
27
}

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

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

A DP whose recurrence reads only the previous row collapses from O(n·m) to O(m) space by alternating two rows. The same trick shrinks LCS, Edit Distance, and 0/1 Knapsack — recognise the single-row look-back and the optimisation is mechanical.

ComplexityO(n·m) time, O(m) space — Still (n+1)(m+1) cell computations → O(n·m) time, but only two rows of length m+1 are retained → O(m) space.

E · Edge cases and pitfalls6a = "abc", b = "" (empty) — m=0; prev[0] stays true through all lowercase rows → YES (delete everything).Explore edge cases

Edge cases handled

a = "abc", b = "" (empty)m=0; prev[0] stays true through all lowercase rows → YES (delete everything).
a = "Xabc", b = "" (empty)Row 'X' sets cur[0] = false (uppercase can't be deleted) → NO.
a = "a"×1000, b = "A"×1000Diagonal of capitalizations fills cur[m] → YES; O(m) space handles the size.

Pitfalls

Reusing a single array in place — reading already-overwritten cur[j-1] corrupts the row; use separate prev/cur.
Forgetting to recompute cur[0] each row — it changes the moment an uppercase letter appears.
Expecting to recover the capitalize/delete choices — O(m) space discards the witness.

Practice

Try the solution yourself

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

Editable code previewpublic String abbreviation(String a, String b) { int n = a.length(), m = b.length(); boolean[][] dp = new boolean[n + 1][m + 1]; dp[0][0] = true; for (int i = 1; i <= n; i++) {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.

Greedy capitalize instead of branching

On a = "Aa", b = "A": greedily capitalizing the lowercase 'a' produces "AA" ≠ "A". You must delete it. Only branching (or the DP's OR) captures this.

Explore the code comparison

Don't write this

# greedy: capitalize whenever it matches
if ca.upper() == b[j]:
    j += 1  # forced, no delete option considered

Write this instead

dp[i][j] = dp[i - 1][j]  # delete option
if ca.upper() == b[j - 1]:
    dp[i][j] = dp[i][j] or dp[i - 1][j - 1]  # capitalize option

Ignoring leftover uppercase letters

When b is exhausted, any remaining uppercase letter in a is undeletable, so the match fails. Returning true unconditionally at j==m is wrong.

Explore the code comparison

Don't write this

if (j == b.length()) return true;  // ignores leftover uppercase in a

Write this instead

if (j == b.length()) {
    for (int k = i; k < a.length(); k++)
        if (Character.isUpperCase(a.charAt(k))) return false;
    return true;
}

Comparing wrong case in lowercase branch

A lowercase letter matches b[j-1] only after capitalization, so you must compare toUpper(a[i-1]), not a[i-1] itself.

Explore the code comparison

Don't write this

if (ca == b.charAt(j - 1)) dp[i][j] |= dp[i-1][j-1];  // never true: ca is lowercase

Write this instead

if (Character.toUpperCase(ca) == b.charAt(j - 1)) dp[i][j] |= dp[i-1][j-1];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-sequence boolean subsequence-matching DP (edit-style grid)

Code pattern to memorize

dp[0][0] = true
for i in 1..n, j in 0..m:
    if a[i-1] is UPPERCASE:
        dp[i][j] = (j>0 && a[i-1]==b[j-1]) ? dp[i-1][j-1] : false
    else  # lowercase
        dp[i][j] = dp[i-1][j]                       # delete a[i-1]
                   || (j>0 && upper(a[i-1])==b[j-1]  # OR capitalize it
                        && dp[i-1][j-1])
answer = dp[n][m]

Rules to remember

1b is always all uppercase — every character of b must be produced by either keeping an uppercase letter of a or capitalizing a lowercase one.
2An uppercase letter in a is non-negotiable: it cannot be deleted, so if it doesn't line up with the current b character the path dies.
3A lowercase letter in a is a free agent: delete it (move down a row, same column) or capitalize it to consume a b character (move diagonally) — only if it uppercases to that character.
4Iterate j from 0, not 1: the j == 0 column answers 'can a[0..i-1] vanish entirely?', which is true only while every letter seen is lowercase.
5Compare Character.toUpperCase(a[i-1]) == b[j-1], never a[i-1] == b[j-1] for the lowercase branch — you're matching the capitalized form.

Use this pattern when

Two strings, asking 'can one transform into the other' under per-character keep/delete/transform rules
One string is a constrained subsequence of the other after a case or filter operation
Characters split into 'mutable' and 'frozen' classes with different allowed moves
A yes/no reachability question over a 2D (prefix-of-a, prefix-of-b) state

Choose another pattern when

You need the minimum number of edits, not a yes/no → Edit Distance (numeric DP)
Both strings are freely editable with insert as well → classic LCS / edit-distance family
Single string, no second target → 1D DP, not this grid
Wildcards `?`/`*` rather than case rules → Wildcard Matching

Interview takeaway

Abbreviation is Edit Distance's boolean cousin: the same prefix-by-prefix grid, but each cell is reachable-or-not instead of a cost, and the allowed moves are dictated by the *case* of the current character. Split characters into mutable (lowercase) and frozen (uppercase) and the recurrence writes itself.

Continue

Transfer the pattern to another problem

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

Transferable patternTwo-sequence boolean reachability DP — Edit Distance's grid with reachable-or-not cells. The case of each character of `a` selects the move set: lowercase = delete or capitalize, uppercase = forced match. Recognise it whenever a transform question pits a 'mutable' character class against a 'frozen' one over two strings.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Edit Distance
Same prefix-by-prefix grid, but cells hold minimum cost (insert/delete/replace) instead of a boolean.
Wildcard Matching
2D boolean DP again, where '*' and '?' set the legal moves instead of letter case.
Longest Common Subsequence
The numeric ancestor of this grid — match consumes both indices, mismatch takes the better neighbour.
Distinct Subsequences
Coming soon
Count (not yes/no) the ways one string forms another as a subsequence — the same grid with addition replacing OR.

Same pattern

←

Wildcard Matching

Continue · Next problem

Candies

mediumDynamic ProgrammingSometimes asked

Abbreviation

Dynamic Programming · 31 of 44 · 12 min

You are given two strings, a and b. You can perform the following operations on string a:

1
Capitalize zero or more of a's lowercase letters.
2
Delete all of the remaining lowercase letters in a.

Return "YES" if a can be transformed into b, otherwise "NO".

In plain English

Examples

Example 1

Input: a = "daBcd", b = "ABC"
Output: YES
Note: Delete the first 'd', capitalize 'a'→'A', keep 'B', capitalize 'c'→'C', delete the last 'd'. Result: "ABC".

Example 2

Input: a = "AbcDE", b = "AFDE"
Output: NO
Note: After keeping 'A', the next needed letter is 'F'. The only lowercase letters available are 'b' and 'c', which capitalize to 'B'/'C', never 'F'. No way to produce 'F'.

Example 3

Input: a = "AbcDE", b = "ABDE"
Output: YES
Note: Keep 'A', capitalize 'b'→'B', delete 'c', keep 'D', keep 'E'. Result: "ABDE".

Constraints

1 ≤ |a|, |b| ≤ 1000
`a` consists of uppercase and lowercase English letters
`b` consists only of uppercase English letters
Uppercase letters in `a` cannot be deleted or changed
Lowercase letters in `a` may each be capitalized or deleted

Clarifying questions4First question: Is `b` guaranteed to be all uppercase?Explore questions

Q1.Is `b` guaranteed to be all uppercase?
Yes. That's why every `b` character must come from a kept-uppercase or a capitalized-lowercase letter of `a`.
Q2.Can I delete uppercase letters in `a` that don't appear in `b`?
No — uppercase letters are frozen. A leftover uppercase letter in `a` with nothing to match in `b` immediately forces 'NO'.
Q3.Must lowercase letters that happen to match `b` be capitalized?
No, and that's the trap. A lowercase letter may need to be *deleted* even when capitalizing it would match, so a later letter can line up. That non-greedy choice is exactly what the DP explores.
Q4.What if |a| < |b|?
Then it's impossible — you can never produce more target characters than `a` has letters to supply. The DP returns false naturally, but you can short-circuit.

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

Whether you model an asymmetric transform (lowercase = delete-or-capitalize, uppercase = must-match) as a 2D boolean reachability DP rather than greedy character matching.

Where candidates slip

How to stand out

Name it as a subsequence/edit-distance-style grid, derive the two branches from the case of the character, handle the j=0 column explicitly, then note the O(m)-space rolling-row optimization.

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 — Recurse on Capitalize / Delete	`O(2ⁿ)`	`O(n)`	State it first to reveal the two branches and the overlapping subproblems, then add memoization or a table.	Read
2	2D Boolean DP — Tabulation (Optimal)Optimal	`O(n·m)`	`O(n·m)`	The answer they want. Phrase it as 'an edit-distance-style grid where each cell is reachable-or-not'.	Read
3	Rolling-Row DP — O(m) Space	`O(n·m)`	`O(m)`	Mention after the 2D table as the memory-tightening step when \|a\| can be large.	Read

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 3

Brute Force — Recurse on Capitalize / Delete

TimeO(2ⁿ)SpaceO(n)

State it first to reveal the two branches and the overlapping subproblems, then add memoization or a table.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk a pointer i over `a` and j over `b`. At each step, what can you do with a[i] depending on whether it's upper or lowercase?

2Hint 2Explore hint

3Hint 3Explore hint

Base cases: if j reached the end of b, the rest of a must be all lowercase (deletable). If i reached the end of a but j hasn't, fail.

A · Core idea

The most literal reading: try to consume b one character at a time while scanning a. Maintain two indices, i into a and j into b.

B · Visual dry run

Interactive dry run

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

a = "aB", b = "B"

Interactive diagram

Recursion forks on every lowercase letter

f(0,0)

Active call / nodeSupporting contextReturned stateNot active

The same (i, j) state can be reached on multiple paths — the exponential waste.

Final resultYES

C · Code with teaching comments

solution.javaJava

Brute Force — Recurse on Capitalize / Delete — reference

4 teaching notes

1
public String abbreviation(String a, String b) {
2
    return solve(a, b, 0, 0) ? "YES" : "NO";
3
}
4
 
5
private boolean solve(String a, String b, int i, int j) {
6
    // All of b produced — success only if every remaining char of a is lowercase
7
    // (deletable).
8
    if (j == b.length()) {
9
        for (int k = i; k < a.length(); k++) {
10
            if (Character.isUpperCase(a.charAt(k))) return false;
11
        }
12
        return true;
13
    }
14
    if (i == a.length()) return false;
15
    char ca = a.charAt(i);
16
    if (Character.isUpperCase(ca)) {
17
        // Uppercase a[i] is frozen: it MUST equal b[j], then both advance.
18
        return ca == b.charAt(j) && solve(a, b, i + 1, j + 1);
19
    }
20
    boolean capitalize = Character.toUpperCase(ca) == b.charAt(j)
21
            && solve(a, b, i + 1, j + 1);
22
    boolean delete = solve(a, b, i + 1, j);
23
    // Either fork succeeding is enough — this OR is why greedy can't replace the
24
    // recursion.
25
    return capitalize || delete;
26
}

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

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

ComplexityO(2ⁿ) time, O(n) space — Each lowercase character can branch two ways, giving up to 2ⁿ leaf paths; recursion depth is O(n) for the call stack.

E · Edge cases and pitfalls3Forgetting to verify leftover characters are lowercase when j hits the end of b.Explore edge cases

Pitfalls

Forgetting to verify leftover characters are lowercase when j hits the end of b.
Allowing the capitalize branch when toUpper(a[i]) != b[j] — an illegal move.
Running it on |a| = 1000 — 2ⁿ never returns; memoize or tabulate.

03.2

Approach 2 of 3 · Optimal

2D Boolean DP — Tabulation (Optimal)

TimeO(n·m)SpaceO(n·m)

The answer they want. Phrase it as 'an edit-distance-style grid where each cell is reachable-or-not'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Define dp[i][j] = can the first i characters of a be transformed into the first j characters of b? You want dp[n][m].

2Hint 2Explore hint

dp[0][0] = true (empty produces empty). Fill the j=0 column: dp[i][0] is true only while a[0..i-1] is all lowercase (everything deletable).

3Hint 3Explore hint

Transition by the case of a[i-1]: uppercase forces dp[i][j] = (a[i-1]==b[j-1]) && dp[i-1][j-1]; lowercase allows delete (dp[i-1][j]) OR capitalize (dp[i-1][j-1] when upper(a[i-1])==b[j-1]).

A · Core idea

Turn the recursion inside-out. Let dp[i][j] mean 'the first `i` characters of `a` can be transformed into the first `j` characters of `b`'. The answer is dp[n][m].

Transition — uppercase a[i-1]. A frozen letter can only be kept, and only if it equals the target: dp[i][j] = (a[i-1] == b[j-1]) && dp[i-1][j-1]. If they differ, the cell is false.

Transition — lowercase a[i-1]. Two ways to reach dp[i][j]:

Delete a[i-1]: the target prefix is unchanged, so inherit dp[i-1][j].
Capitalize a[i-1] to consume b[j-1]: legal only when toUpper(a[i-1]) == b[j-1], contributing dp[i-1][j-1].

Combine with OR: dp[i][j] = dp[i-1][j] || (toUpper(a[i-1]) == b[j-1] && dp[i-1][j-1]).

B · Visual dry run

Interactive dry run

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

a = "daBcd", b = "ABC"

Moves through the DP grid

How to read it:Delete steps down a row; capitalize/match steps diagonally consuming a b character.

Rendering diagram…

Final resultYES

C · Code with teaching comments

solution.javaJava

2D Boolean DP — Tabulation (Optimal) — optimal

5 teaching notes

1
public String abbreviation(String a, String b) {
2
    int n = a.length(), m = b.length();
3
    boolean[][] dp = new boolean[n + 1][m + 1];
4
    // Empty a produces empty b — the seed every path traces back to.
5
    dp[0][0] = true;
6
    for (int i = 1; i <= n; i++) {
7
        char ca = a.charAt(i - 1);
8
        for (int j = 0; j <= m; j++) {
9
            // Frozen letter: only the forced-match move is available.
10
            if (Character.isUpperCase(ca)) {
11
                if (j > 0 && ca == b.charAt(j - 1)) {
12
                    // Uppercase matches b[j-1] → reachable iff the smaller prefix was.
13
                    dp[i][j] = dp[i - 1][j - 1];
14
                }
15
            } else {
16
                // Lowercase delete: drop a[i-1], target prefix unchanged.
17
                dp[i][j] = dp[i - 1][j];
18
                if (j > 0 && Character.toUpperCase(ca) == b.charAt(j - 1)) {
19
                    // OR in the capitalize move when the uppercased letter equals
20
                    // b[j-1].
21
                    dp[i][j] = dp[i][j] || dp[i - 1][j - 1];
22
                }
23
            }
24
        }
25
    }
26
    return dp[n][m] ? "YES" : "NO";
27
}

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

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

ComplexityO(n·m) time, O(n·m) space — Exactly (n+1)(m+1) cells, each filled in O(1) → O(n·m) time. The full table is O(n·m) space.

E · Edge cases and pitfalls7a = "Pi", b = "P" — Keep 'P', delete lowercase 'i' → dp[2][1] inherits dp[1][1]=T → YES.Explore edge cases

Edge cases handled

a = "Pi", b = "P"Keep 'P', delete lowercase 'i' → dp[2][1] inherits dp[1][1]=T → YES.
a = "a", b = "A"Capitalize 'a'→'A': dp[1][1] from dp[0][0]=T → YES.
a = "AB", b = "ABC"Only 2 frozen letters, need 3 targets; dp[2][3] stays false → NO.
a = "Ab", b = "AB" then trailing 'C'An uppercase letter with no matching b position keeps its column false → NO when unmatched.

Pitfalls

Starting the j loop at 1 — loses the delete-the-prefix state in column 0.
Comparing a[i-1] == b[j-1] in the lowercase branch instead of toUpper(a[i-1]) == b[j-1].
Forgetting that an uppercase letter that doesn't match simply leaves the cell false (never OR-in a delete for it).

03.3

Approach 3 of 3

Rolling-Row DP — O(m) Space

TimeO(n·m)SpaceO(m)

Mention after the 2D table as the memory-tightening step when |a| can be large.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

dp[i][*] depends only on dp[i-1][*]. Do you ever read a row older than the previous one?

2Hint 2Explore hint

Keep two 1D arrays, prev and cur, of length m+1. Compute cur from prev each row, then swap.

3Hint 3Explore hint

Watch the j=0 cell of cur: it must encode 'a[0..i-1] all lowercase', so set it before the inner loop based on prev[0] and the case of a[i-1].

A · Core idea

The tabulation only ever reads the immediately previous row, so storing all n+1 rows is wasteful. Keep prev (row i-1) and cur (row i).

The inner loop is identical to the 2D version with dp[i-1][j] → prev[j] and dp[i-1][j-1] → prev[j-1]. After finishing the row, swap prev and cur (and clear cur).

B · Visual dry run

Interactive dry run

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

a = "AbcDE", b = "ABDE"

Two rows leapfrogging down the grid

How to read it:Only prev and cur exist at any time; cur becomes prev each iteration.

Rendering diagram…

Final resultYES

C · Code with teaching comments

solution.javaJava

Rolling-Row DP — O(m) Space — reference

4 teaching notes

1
public String abbreviation(String a, String b) {
2
    int n = a.length(), m = b.length();
3
    boolean[] prev = new boolean[m + 1];
4
    // Row 0, column 0: empty a yields empty b.
5
    prev[0] = true;
6
    for (int i = 1; i <= n; i++) {
7
        char ca = a.charAt(i - 1);
8
        boolean[] cur = new boolean[m + 1];
9
        // Can a[0..i-1] still be fully deleted? Only if it was before AND this char is
10
        // lowercase.
11
        cur[0] = prev[0] && Character.isLowerCase(ca);
12
        for (int j = 1; j <= m; j++) {
13
            if (Character.isUpperCase(ca)) {
14
                // Uppercase forced match reads the diagonal from the previous row.
15
                if (ca == b.charAt(j - 1)) cur[j] = prev[j - 1];
16
            } else {
17
                cur[j] = prev[j];
18
                if (Character.toUpperCase(ca) == b.charAt(j - 1)) {
19
                    cur[j] = cur[j] || prev[j - 1];
20
                }
21
            }
22
        }
23
        // Slide the window: this row becomes the previous row for the next iteration.
24
        prev = cur;
25
    }
26
    return prev[m] ? "YES" : "NO";
27
}

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

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

ComplexityO(n·m) time, O(m) space — Still (n+1)(m+1) cell computations → O(n·m) time, but only two rows of length m+1 are retained → O(m) space.

E · Edge cases and pitfalls6a = "abc", b = "" (empty) — m=0; prev[0] stays true through all lowercase rows → YES (delete everything).Explore edge cases

Edge cases handled

a = "abc", b = "" (empty)m=0; prev[0] stays true through all lowercase rows → YES (delete everything).
a = "Xabc", b = "" (empty)Row 'X' sets cur[0] = false (uppercase can't be deleted) → NO.
a = "a"×1000, b = "A"×1000Diagonal of capitalizations fills cur[m] → YES; O(m) space handles the size.

Pitfalls

Reusing a single array in place — reading already-overwritten cur[j-1] corrupts the row; use separate prev/cur.
Forgetting to recompute cur[0] each row — it changes the moment an uppercase letter appears.
Expecting to recover the capitalize/delete choices — O(m) space discards the witness.

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.

Greedy capitalize instead of branching

On a = "Aa", b = "A": greedily capitalizing the lowercase 'a' produces "AA" ≠ "A". You must delete it. Only branching (or the DP's OR) captures this.

Explore the code comparison

Don't write this

# greedy: capitalize whenever it matches
if ca.upper() == b[j]:
    j += 1  # forced, no delete option considered

Write this instead

dp[i][j] = dp[i - 1][j]  # delete option
if ca.upper() == b[j - 1]:
    dp[i][j] = dp[i][j] or dp[i - 1][j - 1]  # capitalize option

Ignoring leftover uppercase letters

When b is exhausted, any remaining uppercase letter in a is undeletable, so the match fails. Returning true unconditionally at j==m is wrong.

Explore the code comparison

Don't write this

if (j == b.length()) return true;  // ignores leftover uppercase in a

Write this instead

if (j == b.length()) {
    for (int k = i; k < a.length(); k++)
        if (Character.isUpperCase(a.charAt(k))) return false;
    return true;
}

Comparing wrong case in lowercase branch

A lowercase letter matches b[j-1] only after capitalization, so you must compare toUpper(a[i-1]), not a[i-1] itself.

Explore the code comparison

Don't write this

if (ca == b.charAt(j - 1)) dp[i][j] |= dp[i-1][j-1];  // never true: ca is lowercase

Write this instead

if (Character.toUpperCase(ca) == b.charAt(j - 1)) dp[i][j] |= dp[i-1][j-1];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-sequence boolean subsequence-matching DP (edit-style grid)

Code pattern to memorize

dp[0][0] = true
for i in 1..n, j in 0..m:
    if a[i-1] is UPPERCASE:
        dp[i][j] = (j>0 && a[i-1]==b[j-1]) ? dp[i-1][j-1] : false
    else  # lowercase
        dp[i][j] = dp[i-1][j]                       # delete a[i-1]
                   || (j>0 && upper(a[i-1])==b[j-1]  # OR capitalize it
                        && dp[i-1][j-1])
answer = dp[n][m]

Rules to remember

1b is always all uppercase — every character of b must be produced by either keeping an uppercase letter of a or capitalizing a lowercase one.
2An uppercase letter in a is non-negotiable: it cannot be deleted, so if it doesn't line up with the current b character the path dies.
3A lowercase letter in a is a free agent: delete it (move down a row, same column) or capitalize it to consume a b character (move diagonally) — only if it uppercases to that character.
4Iterate j from 0, not 1: the j == 0 column answers 'can a[0..i-1] vanish entirely?', which is true only while every letter seen is lowercase.
5Compare Character.toUpperCase(a[i-1]) == b[j-1], never a[i-1] == b[j-1] for the lowercase branch — you're matching the capitalized form.

Use this pattern when

Two strings, asking 'can one transform into the other' under per-character keep/delete/transform rules
One string is a constrained subsequence of the other after a case or filter operation
Characters split into 'mutable' and 'frozen' classes with different allowed moves
A yes/no reachability question over a 2D (prefix-of-a, prefix-of-b) state

Choose another pattern when

You need the minimum number of edits, not a yes/no → Edit Distance (numeric DP)
Both strings are freely editable with insert as well → classic LCS / edit-distance family
Single string, no second target → 1D DP, not this grid
Wildcards `?`/`*` rather than case rules → Wildcard Matching

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

Edit Distance
Same prefix-by-prefix grid, but cells hold minimum cost (insert/delete/replace) instead of a boolean.
Wildcard Matching
2D boolean DP again, where '*' and '?' set the legal moves instead of letter case.
Longest Common Subsequence
The numeric ancestor of this grid — match consumes both indices, mismatch takes the better neighbour.
Distinct Subsequences
Coming soon
Count (not yes/no) the ways one string forms another as a subsequence — the same grid with addition replacing OR.

Same pattern

←

Wildcard Matching

Continue · Next problem

Candies