LIS & String DP

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

Longest Increasing Subsequence	O(n²)
Longest Common Subsequence	O(n × m)

The Idea

Every DP so far has defined dp[i] around a fixed quantity — dp[i] steps climbed, dp[i][c] value packed into this much capacity. Longest Increasing Subsequence (LIS) defines its state differently: dp[i] means "the length of the longest increasing subsequence that ends exactly at index i." That small shift — anchoring the state to a specific ending point rather than a running total — is the actual new idea this topic introduces, and it shows up again and again in DP once you know to look for it.

String DP extends the same table-of-subproblem-answers idea to two strings at once, one axis per string — exactly the two-axis move Grid DP made from 1D DP, just with string positions standing in for grid coordinates. Longest Common Subsequence (LCS) is the classic case: dp[i][j] is the length of the longest common subsequence between the first i characters of one string and the first j characters of the other, and it's built from the same "look at what's already been solved" neighboring-cell dependency as Grid DP, just phrased in terms of characters instead of paths.

A subsequence skips around — characters stay in order but don't have to be adjacent ("ace" is a subsequence of "abcde"). A substring must be contiguous, no skipping. LIS and LCS are both about subsequences; keep that word choice precise, because "longest common substring" is a real, different problem that this topic's Break It calls out explicitly.

Build It

Two new state shapes: 'ending at i', and 'two strings, two axes'

# LIS: dp[i] = length of the longest increasing subsequence ENDING AT i (not "using the first i")
function lengthOfLIS(arr):
    n = len(arr)
    dp = array of size n, all 1s        // every element is an increasing subsequence of length 1, alone
    for i from 1 to n - 1:
        for j from 0 to i - 1:
            if arr[j] < arr[i]:                       // arr[i] can extend a subsequence ending at j
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)                       // the best subsequence can end ANYWHERE, not necessarily at n-1

# LCS: dp[i][j] = length of the LCS of the first i chars of A and the first j chars of B
function longestCommonSubsequence(a, b):
    dp = 2D array, (len(a) + 1) x (len(b) + 1), all zeros
    for i from 1 to len(a):
        for j from 1 to len(b):
            if a[i - 1] == b[j - 1]:                  // 0-indexed string, 1-indexed table — mind the shift
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(a)][len(b)]

Longest Increasing Subsequence — O(n²)

function lengthOfLIS(arr):
    n = len(arr)
    dp = array of size n, all 1s
    for i from 1 to n - 1:
        for j from 0 to i - 1:
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

For each i, look back at every earlier j: if arr[j] < arr[i], then arr[i] could extend whatever increasing subsequence ends at j, giving a candidate length dp[j] + 1. dp[i] takes the best of all such candidates, or stays 1 if nothing extends. An O(n log n) approach exists (patience sorting with binary search) but isn't required to understand the DP itself — this O(n²) version is the one to master first.

Longest Common Subsequence — O(n × m)

function longestCommonSubsequence(a, b):
    dp = 2D array, (len(a) + 1) x (len(b) + 1), all zeros
    for i from 1 to len(a):
        for j from 1 to len(b):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]      // characters match: extend the diagonal
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])   // no match: best of dropping from either string
    return dp[len(a)][len(b)]

Matching characters extend a common subsequence from the diagonal neighbor — the structural echo of Grid DP's neighbor-cell dependency, just one cell further back when there's a match. A mismatch means "the LCS either doesn't use this character of a, or doesn't use this character of b" — take whichever of those two possibilities is longer.

Know It

LIS's O(n²) comes from the nested loop — for each of n positions, look back at up to n earlier ones — with O(n) space for the dp array (an O(n log n) approach exists but isn't required here). LCS is O(n × m) time and space, the exact same shape as Grid DP: one entry per (i, j) pair, each filled in O(1) from neighbors already computed.

Operation	Time	Space	Why
Longest Increasing Subsequence	O(n²)	O(n)	n positions, each looking back at up to n earlier positions; dp is a single array of length n. (O(n log n) is possible with a different technique, not required here.)
Longest Common Subsequence	O(n × m)	O(n × m)	One dp[i][j] per pair of prefix lengths, each computed in O(1) — the same cost shape as any Grid DP table.

Break It

LIS state confusion: 'ending at i' vs. 'using the first i'

dp[i] is treated as if it means the best LIS somewhere in the first i elements

dp[i] must mean "length of the longest increasing subsequence that ends exactly at index i," not "the best LIS found anywhere among the first i elements." Mixing the two breaks the recurrence: dp[i] = dp[j] + 1 only makes sense when arr[j] genuinely precedes arr[i] in the subsequence, which is only guaranteed under the 'ends at i' definition. It's also why the final answer is max(dp), not dp[n-1] — the longest subsequence can end at any index, not necessarily the last one.

Forgetting the strict less-than rule

the problem allows equal consecutive values but the code still checks arr[j] < arr[i]

"Increasing" by default means strictly increasing — equal adjacent values don't extend the subsequence. Some problem variants ask for non-decreasing instead, which changes the comparison to arr[j] <= arr[i]. Using the wrong one either rejects valid subsequences with duplicate values, or admits subsequences that shouldn't count — always check which the specific problem asks for.

LCS's off-by-one between a 0-indexed string and a 1-indexed table

dp[i][j] is compared against the wrong string index

dp[i][j] conventionally means "the first i characters of a," which — because strings are 0-indexed but the table is sized (len+1) to hold an empty-prefix row/column — corresponds to a[i-1], not a[i]. Comparing a[i] against b[j] instead of a[i-1] against b[j-1] shifts every character check by one and produces a plausible-but-wrong length, often off by exactly one in a way that's easy to miss on short test strings.

Confusing 'subsequence' with 'substring'

the problem says common subsequence but the code assumes the match has to be contiguous, or vice versa

Longest Common Subsequence (not necessarily contiguous — characters can skip around) and Longest Common Substring (must be contiguous) are genuinely different problems with genuinely different recurrences: LCS's mismatch case falls back to max(dp[i-1][j], dp[i][j-1]) (allowing a gap), while a substring's mismatch case must reset to 0 (any gap breaks the substring entirely). Naming the mix-up explicitly is the point — reaching for the LCS recurrence on a substring problem, or vice versa, produces code that runs and returns a confidently wrong number.

Use It

Longest Increasing Subsequence

lengthOfLIS() from Build It, verbatim.

Medium

Longest Common Subsequence

longestCommonSubsequence() from Build It, verbatim.

Medium

Edit Distance

The LCS shape extended with three operations instead of one: on a mismatch, dp[i][j] = 1 + min(insert, delete, replace) = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]).

Medium

Maximum Length of Repeated Subarray

The contiguous 'substring' variant of LCS, deliberate contrast: on a mismatch dp[i][j] resets to 0 instead of falling back to a neighbor, since any gap breaks a contiguous run.

Medium

Longest Palindromic Substring

dp[i][j] = true if the substring from i to j is a palindrome = (s[i] == s[j]) and (j - i < 2 or dp[i+1][j-1]) — fill by increasing substring length, track the longest true span.

Medium

Palindromic Substrings

Same dp[i][j] palindrome table as Longest Palindromic Substring, but count every true entry instead of tracking just the longest.

Medium

Is Subsequence

A greedy two-pointer solves this in O(n) without a table, but it's also the len(s) == LCS(s, t) special case — worth seeing both angles.

Easy

Number of Longest Increasing Subsequence

Extend LIS's dp[i] with a parallel count[i]: when dp[j] + 1 beats dp[i], reset count[i] = count[j]; when it TIES the current dp[i], add count[j] to count[i].

Medium