Distinct subsequences ii

String Dynamic Programming

44.0% acceptance

Feb 25, 2026

1823

Given a string s, return the number of distinct non-empty subsequences of s. Since the answer may be very large, return it modulo 109 + 7. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn distinct_subseq_ii(s: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let mut dp = [0i64; 26];
    for c in s.bytes() {
      let idx = (c - b'a') as usize;
      let total: i64 = dp.iter().sum::<i64>() % MOD;
      dp[idx] = total + 1;
    }
    (dp.iter().sum::<i64>() % MOD) as i32
  }
}