Loading…

mediumDynamic ProgrammingFrequently asked

Common Child

Q: How do you solve Common Child using the Brute Force — Plain Recursion (Exponential) approach?

When to use it: State it first to derive the recurrence, then point out the exponential blow-up from recomputed subproblems to motivate DP. Define `lcs(i, j)` = length of the longest common child of the first `i` characters of `s1` and the first `j` characters of `s2`. **Match case.** If `s1[i-1] == s2[j-1]`, the two prefixes end in the same letter. That letter can always be the last character of an optimal common child of these prefixes, so `lcs(i, j) = lcs(i-1, j-1) + 1`. We never need to consider *not* using a matched ending character — using it is never worse. **Mismatch case.** If the last characters differ, they cannot both be the final matched letter (they're different letters), so at least one of them is not the ending of the optimal child. We don't know which, so we try both: `lcs(i-1, j)` (the optimal child doesn't end with `s1`'s last char) and `lcs(i, j-1)` (it doesn't end with `s2`'s last char), and take the maximum. **Base case.** An empty prefix shares nothing, so `lcs(0, j) = lcs(i, 0) = 0`. **Why it's too slow.** On a full mismatch chain every call spawns two children, producing an exponential tree. But notice there are only `(m+1)(n+1)` distinct `(i, j)` pairs — the tree revisits them enormously. That overlap is the signal to memoise, which turns the recursion into the table below. Time complexity: O(2^(m+n)). Space complexity: O(m+n) recursion stack.

Q: How do you solve Common Child using the Bottom-Up 2D Table (Optimal) approach?

When to use it: The answer they want. Phrase it as 'fill an (m+1)×(n+1) table where each cell is match→diagonal+1, else max of up/left'. Turn the recurrence into a table. Let `dp[i][j]` be the LCS length of `s1[0..i)` and `s2[0..j)`. Row `0` and column `0` are all zeros — those encode the empty-prefix base case. **Filling a cell.** For `i, j ≥ 1`, look at the two current characters `s1[i-1]` and `s2[j-1]`: - If they're **equal**, the best common child of these prefixes is the best child of the shorter prefixes plus this shared letter: `dp[i][j] = dp[i-1][j-1] + 1`. - If they **differ**, the optimal child can't end with both, so drop one and take the better: `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`. Each cell depends only on its diagonal, top, and left neighbours, all filled earlier in a row-major sweep, so a single pass top-to-bottom, left-to-right is enough. **Why the table is correct and minimal.** The recursion above is provably correct; memoising it can't change the answer, only the running time. Because every cell is computed exactly once from O(1) neighbours, the whole table is O(m·n) — comfortably fast for the 5000×5000 worst case (~25M cells). **Space optimisation.** Cell `dp[i][j]` only ever reads row `i` and row `i-1`. So you can keep just two rows (or even one row plus a saved diagonal), dropping memory from O(m·n) to O(min(m,n)). State that as the follow-up — it's the difference between 100 MB and a few KB at the size limit. Time complexity: O(m·n). Space complexity: O(m·n).

Q: How do you solve Common Child using the Two-Row Space Optimisation approach?

When to use it: Mention as the memory-savvy refinement once the 2D table is on the board — useful at the 5000×5000 limit. The full 2D table wastes memory: every cell only depends on the row above it and the cell to its left in the current row. So we keep two rolling arrays. **prev** holds row `i-1`; **curr** is the row `i` we're building. For each `j`: a match uses `prev[j-1] + 1` (the diagonal), a mismatch uses `max(prev[j], curr[j-1])` (up and left). After completing a row, swap `curr` into `prev` and reuse the buffer. **Why it's identical in answer.** We never read any value older than the previous row, so discarding earlier rows is information-lossless. The numbers computed are exactly the same as the full table; only storage changes. **When it matters.** At |s1| = |s2| = 5000, the full `int[5001][5001]` table is ~100 MB. Two rows are ~40 KB. If a judge or interviewer flags memory, this is the fix — and looping the outer dimension over the longer string keeps the rows as short as possible, giving O(min(m,n)). Time complexity: O(m·n). Space complexity: O(min(m,n)).

Dynamic Programming · 39 of 44 · 11 min

A string is said to be a child of another string if it can be formed by deleting zero or more characters from the parent (the remaining characters keep their original order). In other words, a child is a subsequence.

Given two strings s1 and s2 of equal length consisting of uppercase English letters, find the length of the longest string that is a child of both s1 and s2.

In plain English

We want the longest sequence of letters that appears in both strings in the same relative order, allowing gaps. This is exactly the Longest Common Subsequence. The key reframing: at each step compare the last unprocessed character of each prefix — if they match, that letter can end a common child and we recurse on both shorter prefixes; if they differ, at least one of those two characters cannot be part of an optimal child ending here, so we try dropping each and keep the better result.

Examples

Example 1

Input: s1 = "HARRY", s2 = "SALLY"
Output: 2
Note: The longest common child is "AY" (also "RY"... actually "AY": A appears in HARRY at index 1 and in SALLY at index 1; Y is last in both). Length 2.

Example 2

Input: s1 = "AA", s2 = "BB"
Output: 0
Note: No common letters at all, so the only common child is the empty string of length 0.

Example 3

Input: s1 = "SHINCHAN", s2 = "NOHARAAA"
Output: 3
Note: The longest common child is "NHA" — N, H, A all appear in both in that order. Length 3.

Example 4

Input: s1 = "ABCDEF", s2 = "FBDAMN"
Output: 2
Note: "BD" is common to both in order. Length 2.

Constraints

1 ≤ |s1|, |s2| ≤ 5000
|s1| = |s2| (equal length on HackerRank)
Both strings contain only uppercase English letters A–Z
Return the length of the longest common child (a subsequence, not a substring)

Clarifying questions4First question: Is a 'child' a contiguous substring or a subsequence?Explore questions

Q1.Is a 'child' a contiguous substring or a subsequence?
A subsequence — we delete characters and keep order, gaps allowed. This is the single most important clarification; mistaking it for a substring gives a completely different (smaller) answer.
Q2.Do I need to return the actual common child string or just its length?
Just the length for this problem. The actual string can be recovered by backtracking through the table if asked.
Q3.Are the two strings guaranteed to be the same length?
On HackerRank, yes. The algorithm works for unequal lengths too — the table is just (m+1)×(n+1).
Q4.What characters can appear?
Only uppercase A–Z. That doesn't change the algorithm but bounds the alphabet if you wanted to optimise.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A 'common child' of two strings is a string that is a subsequence of both — so the answer is the length of the Longest Common Subsequence (LCS). Build a 2D table dp where dp[i][j] is the LCS length of the first i characters of s1 and the first j of s2. When the current characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). The answer is dp[m][n]. O(m·n) time, O(m·n) space (reducible to O(min(m,n))).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise 'common child' as a thin disguise for Longest Common Subsequence, set up the 2D recurrence correctly, and know subsequence (gaps allowed) differs from substring (contiguous).

Where candidates slip

Solving Longest Common Substring instead (resetting to 0 on mismatch), or adding 1 on a mismatch, or confusing the diagonal/up/left transitions.

How to stand out

Derive the recurrence from the recursion tree, note the overlapping subproblems that justify DP, then mention the O(min(m,n)) two-row space optimisation and how backtracking would recover the actual child string.

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 — Plain Recursion (Exponential)	`O(2^(m+n))`	`O(m+n) recursion stack`	State it first to derive the recurrence, then point out the exponential blow-up from recomputed subproblems to motivate DP.	Read
2	Bottom-Up 2D Table (Optimal)Optimal	`O(m·n)`	`O(m·n)`	The answer they want. Phrase it as 'fill an (m+1)×(n+1) table where each cell is match→diagonal+1, else max of up/left'.	Read
3	Two-Row Space Optimisation	`O(m·n)`	`O(min(m,n))`	Mention as the memory-savvy refinement once the 2D table is on the board — useful at the 5000×5000 limit.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCompare s1[i-1] vs s2[j-1]Equal?YesNoExplore 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 — Plain Recursion (Exponential)

TimeO(2^(m+n))SpaceO(m+n) recursion stack

State it first to derive the recurrence, then point out the exponential blow-up from recomputed subproblems to motivate DP.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Compare the last character of each prefix. If they're equal, that character can extend the common child — recurse on both prefixes minus their last char and add 1.

2Hint 2Explore hint

If the last characters differ, at least one of them isn't used as the final matched character. Try dropping the last char of s1, then dropping the last char of s2, and keep the larger result.

3Hint 3Explore hint

Base case: if either prefix is empty, the LCS is 0. This recursion is correct but recomputes the same (i, j) pair exponentially many times.

A · Core idea

Define lcs(i, j) = length of the longest common child of the first i characters of s1 and the first j characters of s2.

Match case. If s1[i-1] == s2[j-1], the two prefixes end in the same letter. That letter can always be the last character of an optimal common child of these prefixes, so lcs(i, j) = lcs(i-1, j-1) + 1. We never need to consider not using a matched ending character — using it is never worse.

Mismatch case. If the last characters differ, they cannot both be the final matched letter (they're different letters), so at least one of them is not the ending of the optimal child. We don't know which, so we try both: lcs(i-1, j) (the optimal child doesn't end with s1's last char) and lcs(i, j-1) (it doesn't end with s2's last char), and take the maximum.

Base case. An empty prefix shares nothing, so lcs(0, j) = lcs(i, 0) = 0.

Why it's too slow. On a full mismatch chain every call spawns two children, producing an exponential tree. But notice there are only (m+1)(n+1) distinct (i, j) pairs — the tree revisits them enormously. That overlap is the signal to memoise, which turns the recursion into the table below.

B · Visual dry run

Interactive dry run

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

s1 = "AB", s2 = "AC"

Interactive diagram

Recursion tree shows repeated subproblems

lcs(2,2)

Active call / nodeSupporting contextReturned stateNot active

lcs(1,1) is reached by more than one path — the overlap that DP eliminates.

Final result1

C · Code with teaching comments

Reference implementation previewpublic int commonChild(String s1, String s2) { return lcs(s1, s2, s1.length(), s2.length()); } private int lcs(String s1, String s2, int i, int j) {Explore the full code

solution.javaJava

Brute Force — Plain Recursion (Exponential) — reference

4 teaching notes

1
public int commonChild(String s1, String s2) {
2
    return lcs(s1, s2, s1.length(), s2.length());
3
}
4
 
5
private int lcs(String s1, String s2, int i, int j) {
6
    // Empty prefix → no common child possible.
7
    if (i == 0 || j == 0) return 0;
8
    // Characters match → this letter extends the child.
9
    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
10
        // Move diagonally and add the matched character.
11
        return lcs(s1, s2, i - 1, j - 1) + 1;
12
    }
13
    // Mismatch → drop one char from either string, keep the better.
14
    return Math.max(lcs(s1, s2, i - 1, j), lcs(s1, s2, i, j - 1));
15
}

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

D · Why it works and complexityO(2^(m+n)) timeO(m+n) recursion stack spaceOpen the invariant and proofExplore the proof

The recurrence has only two shapes — diagonal+1 on a match, max of up/left on a mismatch. Recognising that there are merely (m+1)(n+1) distinct states is what tells you this exponential recursion collapses into a polynomial DP.

ComplexityO(2^(m+n)) time, O(m+n) recursion stack space — Each mismatch branches into two recursive calls, so the recursion tree has up to 2^(m+n) leaves. The same (i, j) subproblem is solved over and over — that redundancy is exactly what DP removes.

E · Edge cases and pitfalls3Adding 1 on a mismatch — only a match contributes a character.Explore edge cases

Pitfalls

Adding 1 on a mismatch — only a match contributes a character.
Recursing without memoisation at |s| = 5000 — exponential, times out instantly.
Treating it as a substring problem (resetting on mismatch) — solves the wrong question.

03.2

Approach 2 of 3 · Optimal

Bottom-Up 2D Table (Optimal)

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

The answer they want. Phrase it as 'fill an (m+1)×(n+1) table where each cell is match→diagonal+1, else max of up/left'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Memoise the recursion: there are only (m+1)(n+1) distinct (i, j) states, so build a table dp[i][j] instead of recomputing.

2Hint 2Explore hint

Add a row and column of zeros (the empty-prefix base case) so you never index out of bounds and never special-case i==0 or j==0.

3Hint 3Explore hint

Fill row by row: dp[i][j] = dp[i-1][j-1] + 1 on a match, else max(dp[i-1][j], dp[i][j-1]). The answer is dp[m][n].

A · Core idea

Turn the recurrence into a table. Let dp[i][j] be the LCS length of s1[0..i) and s2[0..j). Row 0 and column 0 are all zeros — those encode the empty-prefix base case.

Filling a cell. For i, j ≥ 1, look at the two current characters s1[i-1] and s2[j-1]:

If they're equal, the best common child of these prefixes is the best child of the shorter prefixes plus this shared letter: dp[i][j] = dp[i-1][j-1] + 1.
If they differ, the optimal child can't end with both, so drop one and take the better: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Each cell depends only on its diagonal, top, and left neighbours, all filled earlier in a row-major sweep, so a single pass top-to-bottom, left-to-right is enough.

Why the table is correct and minimal. The recursion above is provably correct; memoising it can't change the answer, only the running time. Because every cell is computed exactly once from O(1) neighbours, the whole table is O(m·n) — comfortably fast for the 5000×5000 worst case (~25M cells).

Space optimisation. Cell dp[i][j] only ever reads row i and row i-1. So you can keep just two rows (or even one row plus a saved diagonal), dropping memory from O(m·n) to O(min(m,n)). State that as the follow-up — it's the difference between 100 MB and a few KB at the size limit.

B · Visual dry run

Interactive dry run

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

s1 = "HARRY", s2 = "SALLY"

Array state

after 'A' row

dp[1][1]=1 (A==A); dp[1][2]=1 (carry)

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Bottom-Up 2D Table (Optimal) — optimal

5 teaching notes

1
public int commonChild(String s1, String s2) {
2
    int m = s1.length(), n = s2.length();
3
    // Extra row/column of zeros encodes the empty-prefix base case.
4
    int[][] dp = new int[m + 1][n + 1];
5
    for (int i = 1; i <= m; i++) {
6
        for (int j = 1; j <= n; j++) {
7
            // Compare the current characters of each prefix.
8
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
9
                // Match → extend the diagonal subproblem by this letter.
10
                dp[i][j] = dp[i - 1][j - 1] + 1;
11
            } else {
12
                // Mismatch → best of dropping s1's or s2's current char.
13
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
14
            }
15
        }
16
    }
17
    // Full-string LCS length — the answer.
18
    return dp[m][n];
19
}

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

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

Each cell reads only its diagonal, top, and left neighbour. That locality is what makes the row-major fill valid in one pass and what enables the two-row O(min(m,n)) space trick: you never look further back than the previous row.

ComplexityO(m·n) time, O(m·n) space — Exactly (m+1)(n+1) cells, each computed in O(1) from three already-known neighbours → O(m·n) time. The full table is O(m·n) space; keeping only the previous and current rows reduces it to O(min(m,n)).

E · Edge cases and pitfalls7s1 = "AA", s2 = "BB" — No matches; every cell takes max of zeros → dp[2][2] = 0.Explore edge cases

Edge cases handled

s1 = "AA", s2 = "BB"No matches; every cell takes max of zeros → dp[2][2] = 0.
s1 = "ABC", s2 = "ABC"Identical strings → matches all along the diagonal → dp[3][3] = 3.
s1 = "A", s2 = "A"Single match → dp[1][1] = 1.
s1 = "ABCDEF", s2 = "FBDAMN"Matches B then D in order → dp[m][n] = 2 ("BD").

Pitfalls

Resetting dp[i][j] to 0 on a mismatch — that solves Longest Common *Substring*, not subsequence.
Allocating a 5001×5001 int table in a language with tight memory — use the two-row optimisation if needed.
Off-by-one: dp indices are 1-based but string indices are 0-based — always read s1[i-1], s2[j-1].

03.3

Approach 3 of 3

Two-Row Space Optimisation

TimeO(m·n)SpaceO(min(m,n))

Mention as the memory-savvy refinement once the 2D table is on the board — useful at the 5000×5000 limit.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Notice dp[i][j] only reads the current row i and the previous row i-1 — rows older than i-1 are never touched again.

2Hint 2Explore hint

Keep just two 1D arrays, prev and curr, of length n+1. After finishing row i, copy curr into prev (or swap the references).

3Hint 3Explore hint

Iterate the outer loop over the longer string and size the rows by the shorter string to make the arrays as small as possible.

A · Core idea

The full 2D table wastes memory: every cell only depends on the row above it and the cell to its left in the current row. So we keep two rolling arrays.

prev holds row i-1; curr is the row i we're building. For each j: a match uses prev[j-1] + 1 (the diagonal), a mismatch uses max(prev[j], curr[j-1]) (up and left). After completing a row, swap curr into prev and reuse the buffer.

Why it's identical in answer. We never read any value older than the previous row, so discarding earlier rows is information-lossless. The numbers computed are exactly the same as the full table; only storage changes.

When it matters. At |s1| = |s2| = 5000, the full int[5001][5001] table is ~100 MB. Two rows are ~40 KB. If a judge or interviewer flags memory, this is the fix — and looping the outer dimension over the longer string keeps the rows as short as possible, giving O(min(m,n)).

B · Visual dry run

Interactive dry run

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

s1 = "AB", s2 = "AC"

Array state

row 'A'

curr filled from prev=[0,0,0]

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

Reference implementation previewpublic int commonChild(String s1, String s2) { if (s1.length() < s2.length()) { String t = s1; s1 = s2; s2 = t; } int m = s1.length(), n = s2.length(); int[] prev = new int[n + 1]; int[] curr = new int[n + 1];Explore the full code

solution.javaJava

Two-Row Space Optimisation — reference

4 teaching notes

1
public int commonChild(String s1, String s2) {
2
    // Loop over the longer string so the rolling rows are as short as possible.
3
    if (s1.length() < s2.length()) { String t = s1; s1 = s2; s2 = t; }
4
    int m = s1.length(), n = s2.length();
5
    int[] prev = new int[n + 1];
6
    int[] curr = new int[n + 1];
7
    for (int i = 1; i <= m; i++) {
8
        for (int j = 1; j <= n; j++) {
9
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
10
                // Match → diagonal (previous row, previous column) plus one.
11
                curr[j] = prev[j - 1] + 1;
12
            } else {
13
                // Mismatch → up (prev[j]) vs left (curr[j-1]).
14
                curr[j] = Math.max(prev[j], curr[j - 1]);
15
            }
16
        }
17
        // Swap buffers; last completed row becomes prev for the next.
18
        int[] tmp = prev; prev = curr; curr = tmp;
19
    }
20
    return prev[n];
21
}

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

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

Rolling two rows is the standard space cut for any grid DP whose recurrence reaches back exactly one row. The moment you confirm 'no cell reads further than row i-1', you've earned the right to throw away everything older.

ComplexityO(m·n) time, O(min(m,n)) space — Same (m·n) cell computations, but at any moment only two rows of length n+1 exist → O(min(m,n)) space when you loop over the longer dimension.

E · Edge cases and pitfalls6s1 = "AA", s2 = "BB" — All mismatches → both rows stay zero → returns 0.Explore edge cases

Edge cases handled

s1 = "AA", s2 = "BB"All mismatches → both rows stay zero → returns 0.
s1 = "ABCDE", s2 = "ACE"Matches A, C, E in order → returns 3 with rows of length 4.
single char stringsOne row iteration; returns 1 if equal else 0.

Pitfalls

Forgetting to reset/overwrite curr[0] — it must stay 0 (the empty-prefix column).
Reading the wrong buffer after the swap — the answer is in prev[n] (post-swap), not curr[n].
Not reusing the buffer (allocating a new row each iteration) — correct but defeats the memory goal.

Practice

Try the solution yourself

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

Editable code previewpublic int commonChild(String s1, String s2) { int m = s1.length(), n = s2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) {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.

Substring instead of subsequence

Resetting dp[i][j] to 0 on a mismatch computes the longest *contiguous* common run. "HARRY"/"SALLY" then returns 1 (just one matching letter run) instead of 2 for the subsequence "AY".

Explore the code comparison

Don't write this

if (s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = 0;  // longest common SUBSTRING, wrong problem

Write this instead

if (s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

Adding 1 on a mismatch

Only a matched character contributes length. Adding 1 in the max branch overcounts and produces lengths longer than either string.

Explore the code comparison

Don't write this

if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 1  # bug: +1 on mismatch

Write this instead

if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

No memoisation on the recursion

The plain recursion revisits each (i, j) exponentially. At |s| = 5000 it never finishes. Either memoise the recursion or write the bottom-up table.

Explore the code comparison

Don't write this

def lcs(i, j):
    if i == 0 or j == 0: return 0
    if s1[i-1] == s2[j-1]: return lcs(i-1, j-1) + 1
    return max(lcs(i-1, j), lcs(i, j-1))  # recomputes everything

Write this instead

from functools import lru_cache
@lru_cache(maxsize=None)
def lcs(i, j):
    if i == 0 or j == 0: return 0
    if s1[i-1] == s2[j-1]: return lcs(i-1, j-1) + 1
    return max(lcs(i-1, j), lcs(i, j-1))

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Longest Common Subsequence — classic 2D table DP

Code pattern to memorize

dp[i][j] = LCS length of s1[0..i) and s2[0..j)
if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
answer = dp[m][n]

Rules to remember

1A 'child' is a subsequence (delete characters, keep order) — NOT a substring. Characters need not be contiguous.
2On a character match, you extend the diagonal: dp[i-1][j-1] + 1. The +1 is the matched character.
3On a mismatch, you drop one character from one string: max(dp[i-1][j], dp[i][j-1]). Never add 1 on a mismatch.
4Use 1-based indexing for the table with an extra row/column of zeros — it removes all the i==0 / j==0 boundary checks.
5You only need the length here, not the string itself, so the standard table suffices (no backtracking required).

Use this pattern when

Two sequences, asked for the longest order-preserving common part
Edit-distance / diff style problems (insert, delete, match)
The words 'subsequence', 'common', 'not necessarily contiguous' appear
You can frame progress as 'consume one character from one or both strings'

Choose another pattern when

It must be **contiguous** → that's Longest Common Substring (reset to 0 on mismatch, track a global max)
Only one string is involved → likely LIS or palind, not LCS
Sequences are huge (10⁶+) and you need exact LCS → O(m·n) may be too slow; bit-parallel / Hunt–Szymanski needed
You need the actual matched string, not its length → keep the table and backtrack from dp[m][n]

Interview takeaway

LCS is the canonical two-sequence grid DP. Match → take the diagonal plus one; mismatch → take the better of dropping a character from either string. Once you internalise this 2×2 cell rule you can solve Edit Distance, Shortest Common Supersequence, and diff tools with the same table.

Continue

Transfer the pattern to another problem

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

Transferable patternLongest Common Subsequence is the prototypical two-sequence grid DP. Match → diagonal + 1; mismatch → max of up and left. Recognise it whenever two sequences are compared for an order-preserving overlap, and remember the contiguous variant (Longest Common Substring) resets to 0 on a mismatch instead.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Sherlock and Cost

Continue · Next problem

Decibinary Numbers

mediumDynamic ProgrammingFrequently asked

Common Child

Dynamic Programming · 39 of 44 · 11 min

Given two strings s1 and s2 of equal length consisting of uppercase English letters, find the length of the longest string that is a child of both s1 and s2.

In plain English

Examples

Example 1

Input: s1 = "HARRY", s2 = "SALLY"
Output: 2
Note: The longest common child is "AY" (also "RY"... actually "AY": A appears in HARRY at index 1 and in SALLY at index 1; Y is last in both). Length 2.

Example 2

Input: s1 = "AA", s2 = "BB"
Output: 0
Note: No common letters at all, so the only common child is the empty string of length 0.

Example 3

Input: s1 = "SHINCHAN", s2 = "NOHARAAA"
Output: 3
Note: The longest common child is "NHA" — N, H, A all appear in both in that order. Length 3.

Example 4

Input: s1 = "ABCDEF", s2 = "FBDAMN"
Output: 2
Note: "BD" is common to both in order. Length 2.

Constraints

1 ≤ |s1|, |s2| ≤ 5000
|s1| = |s2| (equal length on HackerRank)
Both strings contain only uppercase English letters A–Z
Return the length of the longest common child (a subsequence, not a substring)

Clarifying questions4First question: Is a 'child' a contiguous substring or a subsequence?Explore questions

Q1.Is a 'child' a contiguous substring or a subsequence?
A subsequence — we delete characters and keep order, gaps allowed. This is the single most important clarification; mistaking it for a substring gives a completely different (smaller) answer.
Q2.Do I need to return the actual common child string or just its length?
Just the length for this problem. The actual string can be recovered by backtracking through the table if asked.
Q3.Are the two strings guaranteed to be the same length?
On HackerRank, yes. The algorithm works for unequal lengths too — the table is just (m+1)×(n+1).
Q4.What characters can appear?
Only uppercase A–Z. That doesn't change the algorithm but bounds the alphabet if you wanted to optimise.

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 recognise 'common child' as a thin disguise for Longest Common Subsequence, set up the 2D recurrence correctly, and know subsequence (gaps allowed) differs from substring (contiguous).

Where candidates slip

Solving Longest Common Substring instead (resetting to 0 on mismatch), or adding 1 on a mismatch, or confusing the diagonal/up/left transitions.

How to stand out

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 — Plain Recursion (Exponential)	`O(2^(m+n))`	`O(m+n) recursion stack`	State it first to derive the recurrence, then point out the exponential blow-up from recomputed subproblems to motivate DP.	Read
2	Bottom-Up 2D Table (Optimal)Optimal	`O(m·n)`	`O(m·n)`	The answer they want. Phrase it as 'fill an (m+1)×(n+1) table where each cell is match→diagonal+1, else max of up/left'.	Read
3	Two-Row Space Optimisation	`O(m·n)`	`O(min(m,n))`	Mention as the memory-savvy refinement once the 2D table is on the board — useful at the 5000×5000 limit.	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 — Plain Recursion (Exponential)

TimeO(2^(m+n))SpaceO(m+n) recursion stack

State it first to derive the recurrence, then point out the exponential blow-up from recomputed subproblems to motivate DP.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Compare the last character of each prefix. If they're equal, that character can extend the common child — recurse on both prefixes minus their last char and add 1.

2Hint 2Explore hint

If the last characters differ, at least one of them isn't used as the final matched character. Try dropping the last char of s1, then dropping the last char of s2, and keep the larger result.

3Hint 3Explore hint

Base case: if either prefix is empty, the LCS is 0. This recursion is correct but recomputes the same (i, j) pair exponentially many times.

A · Core idea

Define lcs(i, j) = length of the longest common child of the first i characters of s1 and the first j characters of s2.

Base case. An empty prefix shares nothing, so lcs(0, j) = lcs(i, 0) = 0.

B · Visual dry run

Interactive dry run

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

s1 = "AB", s2 = "AC"

Interactive diagram

Recursion tree shows repeated subproblems

lcs(2,2)

Active call / nodeSupporting contextReturned stateNot active

lcs(1,1) is reached by more than one path — the overlap that DP eliminates.

Final result1

C · Code with teaching comments

solution.javaJava

Brute Force — Plain Recursion (Exponential) — reference

4 teaching notes

1
public int commonChild(String s1, String s2) {
2
    return lcs(s1, s2, s1.length(), s2.length());
3
}
4
 
5
private int lcs(String s1, String s2, int i, int j) {
6
    // Empty prefix → no common child possible.
7
    if (i == 0 || j == 0) return 0;
8
    // Characters match → this letter extends the child.
9
    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
10
        // Move diagonally and add the matched character.
11
        return lcs(s1, s2, i - 1, j - 1) + 1;
12
    }
13
    // Mismatch → drop one char from either string, keep the better.
14
    return Math.max(lcs(s1, s2, i - 1, j), lcs(s1, s2, i, j - 1));
15
}

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

D · Why it works and complexityO(2^(m+n)) timeO(m+n) recursion stack spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Adding 1 on a mismatch — only a match contributes a character.Explore edge cases

Pitfalls

Adding 1 on a mismatch — only a match contributes a character.
Recursing without memoisation at |s| = 5000 — exponential, times out instantly.
Treating it as a substring problem (resetting on mismatch) — solves the wrong question.

03.2

Approach 2 of 3 · Optimal

Bottom-Up 2D Table (Optimal)

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

The answer they want. Phrase it as 'fill an (m+1)×(n+1) table where each cell is match→diagonal+1, else max of up/left'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Memoise the recursion: there are only (m+1)(n+1) distinct (i, j) states, so build a table dp[i][j] instead of recomputing.

2Hint 2Explore hint

Add a row and column of zeros (the empty-prefix base case) so you never index out of bounds and never special-case i==0 or j==0.

3Hint 3Explore hint

Fill row by row: dp[i][j] = dp[i-1][j-1] + 1 on a match, else max(dp[i-1][j], dp[i][j-1]). The answer is dp[m][n].

A · Core idea

Turn the recurrence into a table. Let dp[i][j] be the LCS length of s1[0..i) and s2[0..j). Row 0 and column 0 are all zeros — those encode the empty-prefix base case.

Filling a cell. For i, j ≥ 1, look at the two current characters s1[i-1] and s2[j-1]:

If they're equal, the best common child of these prefixes is the best child of the shorter prefixes plus this shared letter: dp[i][j] = dp[i-1][j-1] + 1.
If they differ, the optimal child can't end with both, so drop one and take the better: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Each cell depends only on its diagonal, top, and left neighbours, all filled earlier in a row-major sweep, so a single pass top-to-bottom, left-to-right is enough.

B · Visual dry run

Interactive dry run

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

s1 = "HARRY", s2 = "SALLY"

Array state

after 'A' row

dp[1][1]=1 (A==A); dp[1][2]=1 (carry)

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Bottom-Up 2D Table (Optimal) — optimal

5 teaching notes

1
public int commonChild(String s1, String s2) {
2
    int m = s1.length(), n = s2.length();
3
    // Extra row/column of zeros encodes the empty-prefix base case.
4
    int[][] dp = new int[m + 1][n + 1];
5
    for (int i = 1; i <= m; i++) {
6
        for (int j = 1; j <= n; j++) {
7
            // Compare the current characters of each prefix.
8
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
9
                // Match → extend the diagonal subproblem by this letter.
10
                dp[i][j] = dp[i - 1][j - 1] + 1;
11
            } else {
12
                // Mismatch → best of dropping s1's or s2's current char.
13
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
14
            }
15
        }
16
    }
17
    // Full-string LCS length — the answer.
18
    return dp[m][n];
19
}

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

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

E · Edge cases and pitfalls7s1 = "AA", s2 = "BB" — No matches; every cell takes max of zeros → dp[2][2] = 0.Explore edge cases

Edge cases handled

s1 = "AA", s2 = "BB"No matches; every cell takes max of zeros → dp[2][2] = 0.
s1 = "ABC", s2 = "ABC"Identical strings → matches all along the diagonal → dp[3][3] = 3.
s1 = "A", s2 = "A"Single match → dp[1][1] = 1.
s1 = "ABCDEF", s2 = "FBDAMN"Matches B then D in order → dp[m][n] = 2 ("BD").

Pitfalls

Resetting dp[i][j] to 0 on a mismatch — that solves Longest Common *Substring*, not subsequence.
Allocating a 5001×5001 int table in a language with tight memory — use the two-row optimisation if needed.
Off-by-one: dp indices are 1-based but string indices are 0-based — always read s1[i-1], s2[j-1].

03.3

Approach 3 of 3

Two-Row Space Optimisation

TimeO(m·n)SpaceO(min(m,n))

Mention as the memory-savvy refinement once the 2D table is on the board — useful at the 5000×5000 limit.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Notice dp[i][j] only reads the current row i and the previous row i-1 — rows older than i-1 are never touched again.

2Hint 2Explore hint

Keep just two 1D arrays, prev and curr, of length n+1. After finishing row i, copy curr into prev (or swap the references).

3Hint 3Explore hint

Iterate the outer loop over the longer string and size the rows by the shorter string to make the arrays as small as possible.

A · Core idea

The full 2D table wastes memory: every cell only depends on the row above it and the cell to its left in the current row. So we keep two rolling arrays.

B · Visual dry run

Interactive dry run

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

s1 = "AB", s2 = "AC"

Array state

row 'A'

curr filled from prev=[0,0,0]

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

solution.javaJava

Two-Row Space Optimisation — reference

4 teaching notes

1
public int commonChild(String s1, String s2) {
2
    // Loop over the longer string so the rolling rows are as short as possible.
3
    if (s1.length() < s2.length()) { String t = s1; s1 = s2; s2 = t; }
4
    int m = s1.length(), n = s2.length();
5
    int[] prev = new int[n + 1];
6
    int[] curr = new int[n + 1];
7
    for (int i = 1; i <= m; i++) {
8
        for (int j = 1; j <= n; j++) {
9
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
10
                // Match → diagonal (previous row, previous column) plus one.
11
                curr[j] = prev[j - 1] + 1;
12
            } else {
13
                // Mismatch → up (prev[j]) vs left (curr[j-1]).
14
                curr[j] = Math.max(prev[j], curr[j - 1]);
15
            }
16
        }
17
        // Swap buffers; last completed row becomes prev for the next.
18
        int[] tmp = prev; prev = curr; curr = tmp;
19
    }
20
    return prev[n];
21
}

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

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

ComplexityO(m·n) time, O(min(m,n)) space — Same (m·n) cell computations, but at any moment only two rows of length n+1 exist → O(min(m,n)) space when you loop over the longer dimension.

E · Edge cases and pitfalls6s1 = "AA", s2 = "BB" — All mismatches → both rows stay zero → returns 0.Explore edge cases

Edge cases handled

s1 = "AA", s2 = "BB"All mismatches → both rows stay zero → returns 0.
s1 = "ABCDE", s2 = "ACE"Matches A, C, E in order → returns 3 with rows of length 4.
single char stringsOne row iteration; returns 1 if equal else 0.

Pitfalls

Forgetting to reset/overwrite curr[0] — it must stay 0 (the empty-prefix column).
Reading the wrong buffer after the swap — the answer is in prev[n] (post-swap), not curr[n].
Not reusing the buffer (allocating a new row each iteration) — correct but defeats the memory goal.

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.

Substring instead of subsequence

Resetting dp[i][j] to 0 on a mismatch computes the longest *contiguous* common run. "HARRY"/"SALLY" then returns 1 (just one matching letter run) instead of 2 for the subsequence "AY".

Explore the code comparison

Don't write this

if (s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = 0;  // longest common SUBSTRING, wrong problem

Write this instead

if (s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

Adding 1 on a mismatch

Only a matched character contributes length. Adding 1 in the max branch overcounts and produces lengths longer than either string.

Explore the code comparison

Don't write this

if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 1  # bug: +1 on mismatch

Write this instead

if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

No memoisation on the recursion

The plain recursion revisits each (i, j) exponentially. At |s| = 5000 it never finishes. Either memoise the recursion or write the bottom-up table.

Explore the code comparison

Don't write this

def lcs(i, j):
    if i == 0 or j == 0: return 0
    if s1[i-1] == s2[j-1]: return lcs(i-1, j-1) + 1
    return max(lcs(i-1, j), lcs(i, j-1))  # recomputes everything

Write this instead

from functools import lru_cache
@lru_cache(maxsize=None)
def lcs(i, j):
    if i == 0 or j == 0: return 0
    if s1[i-1] == s2[j-1]: return lcs(i-1, j-1) + 1
    return max(lcs(i-1, j), lcs(i, j-1))

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Longest Common Subsequence — classic 2D table DP

Code pattern to memorize

dp[i][j] = LCS length of s1[0..i) and s2[0..j)
if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
answer = dp[m][n]

Rules to remember

1A 'child' is a subsequence (delete characters, keep order) — NOT a substring. Characters need not be contiguous.
2On a character match, you extend the diagonal: dp[i-1][j-1] + 1. The +1 is the matched character.
3On a mismatch, you drop one character from one string: max(dp[i-1][j], dp[i][j-1]). Never add 1 on a mismatch.
4Use 1-based indexing for the table with an extra row/column of zeros — it removes all the i==0 / j==0 boundary checks.
5You only need the length here, not the string itself, so the standard table suffices (no backtracking required).

Use this pattern when

Two sequences, asked for the longest order-preserving common part
Edit-distance / diff style problems (insert, delete, match)
The words 'subsequence', 'common', 'not necessarily contiguous' appear
You can frame progress as 'consume one character from one or both strings'

Choose another pattern when

It must be **contiguous** → that's Longest Common Substring (reset to 0 on mismatch, track a global max)
Only one string is involved → likely LIS or palind, not LCS
Sequences are huge (10⁶+) and you need exact LCS → O(m·n) may be too slow; bit-parallel / Hunt–Szymanski needed
You need the actual matched string, not its length → keep the table and backtrack from dp[m][n]

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

Same pattern

←

Sherlock and Cost

Continue · Next problem

Decibinary Numbers