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 (anchor the state to a specific ending point instead of a running total) is the actual new idea that this topic introduces. It appears 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. This is exactly the two-axis move that Grid DP made from 1D DP, with string positions in place of 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. It is built from the same "look at what has already been solved" neighboring-cell dependency as Grid DP, but phrased in terms of characters instead of paths.

A subsequence skips around. The characters stay in order but do not have to be next to each other ("ace" is a subsequence of "abcde"). A substring must be contiguous, with 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 alone is an increasing subsequence of length 1
    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 only 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] can extend the increasing subsequence that ends at j, which gives 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 you do not need it 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 a drop from either string
    return dp[len(a)][len(b)]

Matching characters extend a common subsequence from the diagonal neighbor, the structural echo of the neighbor-cell dependency in Grid DP, one cell further back when there is a match. A mismatch means "the LCS either does not use this character of a, or does not use this character of b". Take whichever of those two possibilities is longer.

Know It

The O(n²) of LIS comes from the nested loop: for each of n positions, look back at up to n earlier positions. It uses O(n) space for the dp array (an O(n log n) approach exists but is not 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)	There are n positions, each one a look 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). This is 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 "the length of the longest increasing subsequence that ends exactly at index i", not "the best LIS found anywhere among the first i elements". To mix the two breaks the recurrence. dp[i] = dp[j] + 1 makes sense only when arr[j] genuinely comes before arr[i] in the subsequence, which is guaranteed only under the 'ends at i' definition. It is 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 do not extend the subsequence. Some problem variants ask for non-decreasing instead, which changes the comparison to arr[j] <= arr[i]. The wrong one either rejects valid subsequences with duplicate values, or admits subsequences that should not count. Always check which one 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". Because strings are 0-indexed but the table is sized (len+1) to hold an empty-prefix row and column, this corresponds to a[i-1], not a[i]. To compare 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 is easy to miss on short test strings.

Confusing 'subsequence' with 'substring'

the problem says common subsequence but the code assumes that the match must be contiguous, or the reverse

Longest Common Subsequence (not necessarily contiguous: the characters can skip around) and Longest Common Substring (must be contiguous) are genuinely different problems with genuinely different recurrences. The mismatch case of LCS falls back to max(dp[i-1][j], dp[i][j-1]) (a gap is allowed). The mismatch case of a substring must reset to 0 (any gap breaks the substring completely). To name the mix-up explicitly is the point. To use the LCS recurrence on a substring problem, or the reverse, produces code that runs and returns a confidently wrong number.

Use It

Longest Increasing Subsequence

Use lengthOfLIS() from Build It, exactly.

Medium

Longest Common Subsequence

Use longestCommonSubsequence() from Build It, exactly.

Medium

Edit Distance

This is 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

This is the contiguous 'substring' variant of LCS, a deliberate contrast. On a mismatch, dp[i][j] resets to 0 instead of a fall back to a neighbor, because 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

Use the same dp[i][j] palindrome table as Longest Palindromic Substring, but count every true entry instead of a track of only the longest.

Medium

Is Subsequence

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

Easy

Number of Longest Increasing Subsequence

Extend the dp[i] of LIS 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