Longest common subsequence

String Dynamic Programming

58.9% acceptance

Feb 25, 2026

14984

246

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde". A common subsequence of two strings is a subsequence that is common to both strings.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
    let (m, n) = (text1.len(), text2.len());
    let s1: Vec<u8> = text1.bytes().collect();
    let s2: Vec<u8> = text2.bytes().collect();
    let mut dp = vec![vec![0i32; n + 1]; m + 1];
    for i in 1..=m {
      for j in 1..=n {
        dp[i][j] = if s1[i-1] == s2[j-1] {
          dp[i-1][j-1] + 1
        } else {
          dp[i-1][j].max(dp[i][j-1])
        };
      }
    }
    dp[m][n]
  }
}