LeetCode Entry

115. Distinct Subsequences

06.09.2026 hard 2026 kotlin rust

Count target substrings

115. Distinct Subsequences hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1474

Problem TLDR

Count target substrings

Intuition

DFS+memo, subproblem starts with suffixes of the string and the target.

Approach

• top-down then rewrite to bottom-up

Complexity

• Time complexity: \(O(n^2)\)

• Space complexity: \(O(n)\)

Code

    fun numDistinct(s: String, t: String): Int {
        val dp = IntArray(t.length+1); dp[0] = 1
        for (c in s) for (j in t.length - 1 downTo 0)
            if (c == t[j]) dp[j + 1] += dp[j]
        return dp[t.length]
    }

    pub fn num_distinct(s: String, t: String) -> i32 {
        let mut dp = [0; 1001]; dp[0] = 1;
        let (s, t) = (s.as_bytes(), t.as_bytes());
        for &c in s { for j in (0..t.len()).rev() {
            if c == t[j] { dp[j + 1] += dp[j] }
        }} dp[t.len()]
    }