LeetCode Entry

940. Distinct Subsequences II

07.09.2026 hard 2026 kotlin rust

Count uniq substrings

940. Distinct Subsequences II hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1475

Problem TLDR

Count uniq substrings

Intuition

DFS+memo. Take or skip. Do not take repeating consequent letters.

Approach

• top-down then rewrite to bottom-up

Complexity

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

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

Code

    fun distinctSubseqII(s: String) = LongArray(26).apply {
        for (c in s) this[c - 'a'] = (sum() + 1) % 1_000_000_007
    }.sum() % 1_000_000_007

    pub fn distinct_subseq_ii(s: String) -> i32 {
        let mut d = [0; 128];
        for b in s.bytes() { d[b as usize] = (d.iter().sum::<u64>() + 1) % 1000000007 }
        (d.iter().sum::<u64>() % 1000000007) as _
    }