1143. Longest Common Subsequence (Medium)

Problem

Given two strings text1 and text2, return the length of their longest common subsequence (LCS). A subsequence is a sequence that can be derived from another by deleting zero or more elements without changing relative order.

Example

text1 = "abcde", text2 = "ace" → 3 ("ace")
text1 = "abc", text2 = "abc" → 3
text1 = "abc", text2 = "def" → 0

LeetCode 1143 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Recursive

f(i, j) = LCS of text1[i:] and text2[j:].

def longest_common_subsequence(text1, text2):
    def f(i, j):
        if i == len(text1) or j == len(text2):  # L1: O(1) base case
            return 0
        if text1[i] == text2[j]:                # L2: O(1) char match
            return 1 + f(i + 1, j + 1)          # L3: one recursive call (diagonal)
        return max(f(i + 1, j), f(i, j + 1))   # L4: two recursive calls
    return f(0, 0)

function longestCommonSubsequence(text1: string, text2: string): number {
    function f(i: number, j: number): number {
        if (i === text1.length || j === text2.length) return 0;  // L1: O(1) base case
        if (text1[i] === text2[j])                               // L2: O(1) char match
            return 1 + f(i + 1, j + 1);                          // L3: one recursive call (diagonal)
        return Math.max(f(i + 1, j), f(i, j + 1));              // L4: two recursive calls
    }
    return f(0, 0);
}

func longestCommonSubsequence(text1 string, text2 string) int {
    max := func(a, b int) int { if a > b { return a }; return b }
    var f func(i, j int) int
    f = func(i, j int) int {
        if i == len(text1) || j == len(text2) { return 0 } // L1: O(1) base case
        if text1[i] == text2[j] {                          // L2: O(1) char match
            return 1 + f(i+1, j+1)                         // L3: one recursive call (diagonal)
        }
        return max(f(i+1, j), f(i, j+1))                   // L4: two recursive calls
    }
    return f(0, 0)
}

final class Solution {
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        let a = Array(text1), b = Array(text2)
        func solve(_ i: Int, _ j: Int) -> Int { if i == a.count || j == b.count { return 0 }; return a[i] == b[j] ? 1 + solve(i + 1, j + 1) : max(solve(i + 1, j), solve(i, j + 1)) }
        return solve(0, 0)
    }
}

Where the time goes, line by line

Variables: m = len(text1), n = len(text2).

Line	Per-call cost	Times executed	Contribution
L1-L2 (base + match check)	$O(1)$	per call	$O(1)$ each
L3 (one call on match)	$O(1)$ work + 1 call	per match	included below
L4 (two calls on mismatch)	$O(1)$ work + 2 calls	worst case every call	$O(2^{m+n})$ ← dominates

Every mismatch doubles the call tree. Without memoization the same (i, j) is recomputed at every overlapping node.

Complexity

Time: $O(2^{m+n})$ , driven by L4 double-branching on mismatches.
Space: $O(m + n)$ recursion depth.

Approach 2: 2-D bottom-up DP (canonical)

dp[i][j] = LCS of text1[:i] and text2[:j]. dp[i][j] depends on dp[i-1][j-1], dp[i-1][j], dp[i][j-1].

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)                        # L1: O(1)
    dp = [[0] * (n + 1) for _ in range(m + 1)]          # L2: O(m*n) table init (zeros = base cases)
    for i in range(1, m + 1):                            # L3: outer loop O(m)
        for j in range(1, n + 1):                        # L4: inner loop O(n)
            if text1[i - 1] == text2[j - 1]:            # L5: O(1) char match
                dp[i][j] = 1 + dp[i - 1][j - 1]        # L6: O(1) diagonal + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # L7: O(1) max of up/left
    return dp[m][n]                                      # L8: O(1) answer

function longestCommonSubsequence(text1: string, text2: string): number {
    const m = text1.length, n = text2.length;                          // L1: O(1)
    const dp: number[][] = Array.from({ length: m + 1 }, () =>
        new Array(n + 1).fill(0));                                     // L2: O(m*n) table init
    for (let i = 1; i <= m; i++) {                                     // L3: outer loop O(m)
        for (let j = 1; j <= n; j++) {                                 // L4: inner loop O(n)
            if (text1[i - 1] === text2[j - 1])                        // L5: O(1) char match
                dp[i][j] = 1 + dp[i - 1][j - 1];                     // L6: O(1) diagonal + 1
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);     // L7: O(1) max of up/left
        }
    }
    return dp[m][n];                                                   // L8: O(1) answer
}

func longestCommonSubsequence(text1 string, text2 string) int {
    max := func(a, b int) int { if a > b { return a }; return b }
    m, n := len(text1), len(text2)                  // L1: O(1)
    dp := make([][]int, m+1)
    for i := range dp { dp[i] = make([]int, n+1) } // L2: O(m*n) table init
    for i := 1; i <= m; i++ {                       // L3: outer loop O(m)
        for j := 1; j <= n; j++ {                   // L4: inner loop O(n)
            if text1[i-1] == text2[j-1] {           // L5: O(1) char match
                dp[i][j] = 1 + dp[i-1][j-1]        // L6: O(1) diagonal + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // L7: O(1) max of up/left
            }
        }
    }
    return dp[m][n]                                 // L8: O(1) answer
}

Where the time goes, line by line

Variables: m = len(text1), n = len(text2).

Line	Per-call cost	Times executed	Contribution
L1-L2 (init)	$O(1)$ or $O(m·n)$	1	$O(m · n)$
L3+L4 (double loop)	$O(1)$ body	m · n	$O(m · n)$ ← dominates
L5-L7 (cell fill)	$O(1)$	once per cell	included above

Each cell fill is a single comparison plus one or two table lookups, all $O(1)$ . The double loop at L3/L4 drives the total.

Complexity

Time: $O(m · n)$ , driven by L3/L4 (the full double loop).
Space: $O(m · n)$ for the DP table.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        let a = Array(text1), b = Array(text2); var dp = Array(repeating: Array(repeating: 0, count: b.count + 1), count: a.count + 1)
        if !a.isEmpty && !b.isEmpty { for i in stride(from: a.count - 1, through: 0, by: -1) { for j in stride(from: b.count - 1, through: 0, by: -1) { dp[i][j] = a[i] == b[j] ? 1 + dp[i + 1][j + 1] : max(dp[i + 1][j], dp[i][j + 1]) } } }
        return dp[0][0]
    }
}

Approach 3: 1-D rolling array (optimal space)

Keep two rows, current and previous. Or one row with a diagonal scratch scalar.

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)         # L1: O(1)
    if m < n:                             # L2: O(1) ensure text1 is longer (minimize space)
        text1, text2 = text2, text1
        m, n = n, m
    prev = [0] * (n + 1)                  # L3: O(n) init previous row
    for i in range(1, m + 1):            # L4: outer loop O(m)
        curr = [0] * (n + 1)             # L5: O(n) allocate current row
        for j in range(1, n + 1):        # L6: inner loop O(n)
            if text1[i - 1] == text2[j - 1]:     # L7: O(1) char match
                curr[j] = 1 + prev[j - 1]         # L8: O(1) diagonal + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])  # L9: O(1) max of up/left
        prev = curr                       # L10: O(1) roll the row
    return prev[n]                        # L11: O(1) answer

function longestCommonSubsequence(text1: string, text2: string): number {
    let s1 = text1, s2 = text2;
    if (s1.length < s2.length) [s1, s2] = [s2, s1];                   // L2: minimize space
    const m = s1.length, n = s2.length;
    let prev: number[] = new Array(n + 1).fill(0);                    // L3: O(n) init previous row
    for (let i = 1; i <= m; i++) {                                     // L4: outer loop O(m)
        const curr: number[] = new Array(n + 1).fill(0);              // L5: O(n) current row
        for (let j = 1; j <= n; j++) {                                 // L6: inner loop O(n)
            if (s1[i - 1] === s2[j - 1])                              // L7: O(1) char match
                curr[j] = 1 + prev[j - 1];                            // L8: O(1) diagonal + 1
            else
                curr[j] = Math.max(prev[j], curr[j - 1]);             // L9: O(1) max of up/left
        }
        prev = curr;                                                   // L10: O(1) roll
    }
    return prev[n];                                                    // L11: O(1) answer
}

func longestCommonSubsequence(text1 string, text2 string) int {
    max := func(a, b int) int { if a > b { return a }; return b }
    m, n := len(text1), len(text2)         // L1: O(1)
    if m < n {                             // L2: O(1) ensure text1 is longer
        text1, text2 = text2, text1
        m, n = n, m
    }
    prev := make([]int, n+1)               // L3: O(n) init previous row
    for i := 1; i <= m; i++ {             // L4: outer loop O(m)
        curr := make([]int, n+1)           // L5: O(n) allocate current row
        for j := 1; j <= n; j++ {         // L6: inner loop O(n)
            if text1[i-1] == text2[j-1] { // L7: O(1) char match
                curr[j] = 1 + prev[j-1]   // L8: O(1) diagonal + 1
            } else {
                curr[j] = max(prev[j], curr[j-1]) // L9: O(1) max of up/left
            }
        }
        prev = curr                        // L10: O(1) roll the row
    }
    return prev[n]                         // L11: O(1) answer
}

Where the time goes, line by line

Variables: m = len(text1), n = len(text2) (after the swap so m >= n).

Line	Per-call cost	Times executed	Contribution
L1-L3 (init)	$O(n)$	1	$O(n)$
L5 (row alloc)	$O(n)$	m	$O(m · n)$
L4+L6 (double loop)	$O(1)$ body	m · n	$O(m · n)$ ← dominates
L7-L9 (cell fill)	$O(1)$	once per cell	included above

Same time as 2-D DP but space is $O(n)$ (two rows of size n). The swap at L2 ensures we allocate the shorter dimension.

Complexity

Time: $O(m · n)$ , driven by L4/L6 (the double loop).
Space: $O(min(m, n)$ ) for the two rolling rows.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        let a = Array(text1), b = Array(text2); var next = Array(repeating: 0, count: b.count + 1)
        if !a.isEmpty && !b.isEmpty { for i in stride(from: a.count - 1, through: 0, by: -1) { var current = next; for j in stride(from: b.count - 1, through: 0, by: -1) { current[j] = a[i] == b[j] ? 1 + next[j + 1] : max(next[j], current[j + 1]) }; next = current } }
        return next[0]
    }
}

Summary

Approach	Time	Space
Recursive	$O(2^{m+n})$	$O(m+n)$
2-D DP	$O(m · n)$	$O(m · n)$
1-D rolling DP	$O(m · n)$	$O(min(m, n)$ )

LCS is the prototype of the “compare two sequences” DP. Its recurrence pattern, if match then diagonal+1 else max(up, left), shows up in Edit Distance, Shortest Common Supersequence, Minimum ASCII Delete Sum.

Test cases

# Quick smoke tests, paste into a REPL or save as test_1143.py and run.
# Uses the canonical implementation (Approach 2: 2-D bottom-up DP).

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

def _run_tests():
    # problem statement examples
    assert longest_common_subsequence("abcde", "ace") == 3
    assert longest_common_subsequence("abc", "abc") == 3
    assert longest_common_subsequence("abc", "def") == 0
    # edge: empty strings
    assert longest_common_subsequence("", "abc") == 0
    assert longest_common_subsequence("abc", "") == 0
    # single char match
    assert longest_common_subsequence("a", "a") == 1
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function longestCommonSubsequence(text1: string, text2: string): number {
    const m = text1.length, n = text2.length;
    const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++)
        for (let j = 1; j <= n; j++)
            if (text1[i - 1] === text2[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    return dp[m][n];
}

console.assert(longestCommonSubsequence("abcde", "ace") === 3);
console.assert(longestCommonSubsequence("abc", "abc") === 3);
console.assert(longestCommonSubsequence("abc", "def") === 0);
console.assert(longestCommonSubsequence("", "abc") === 0);
console.assert(longestCommonSubsequence("abc", "") === 0);
console.assert(longestCommonSubsequence("a", "a") === 1);
console.log("all tests pass");

package main

import "fmt"

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp { dp[i] = make([]int, n+1) }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = 1 + dp[i-1][j-1]
            } else if dp[i-1][j] > dp[i][j-1] {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = dp[i][j-1]
            }
        }
    }
    return dp[m][n]
}

func main() {
    if longestCommonSubsequence("abcde", "ace") != 3 { panic("fail") }
    if longestCommonSubsequence("abc", "abc") != 3 { panic("fail") }
    if longestCommonSubsequence("abc", "def") != 0 { panic("fail") }
    if longestCommonSubsequence("", "abc") != 0 { panic("fail") }
    if longestCommonSubsequence("abc", "") != 0 { panic("fail") }
    if longestCommonSubsequence("a", "a") != 1 { panic("fail") }
    fmt.Println("all tests pass")
}

Strings, sequence alignment DP

Dynamic Programming, state-and-transition tactics for solving overlapping subproblems with cached answers.
Sequence DP, order-aware DP tactics for strings and arrays where prefixes or positions define reusable states.
Tabulation, bottom-up DP tactics for filling states in dependency order without recursion.

1143. Longest Common Subsequence (Medium)

Problem

Try it yourself

Approach 1: Recursive

Approach 2: 2-D bottom-up DP (canonical)

Approach 3: 1-D rolling array (optimal space)

Summary

Test cases

Related data structures

Related concepts