Distinct subsequences

String Dynamic Programming

51.5% acceptance

Jan 12, 2026

7369

321

Given two strings s and t, return the number of distinct subsequences of s which equals t. The test cases are generated so that the answer fits on a 32-bit signed integer.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_distinct(s: String, t: String) -> i32 {
    let s_bytes = s.as_bytes();
    let t_bytes = t.as_bytes();
    let n = t_bytes.len();
    
    if n > s_bytes.len() {
      return 0;
    }
    
    let mut dp = vec![0u64; n + 1];
    dp[0] = 1;
    
    for &sc in s_bytes {
      for j in (1..=n).rev() {
        if sc == t_bytes[j - 1] {
          dp[j] += dp[j - 1];
        }
      }
    }
    
    dp[n] as i32
  }
}