LeetCode 940. 不同的子序列 II

Categories:

题目描述
思路分析
1. 解法一：DP + 最近贡献（推荐）
相似题目

题目描述

✅ 940. 不同的子序列 II

思路分析

解法一：DP + 最近贡献（推荐）

核心思路：

设 total 表示当前不同子序列数量（含空串）。

遍历字符 c，新总数为 total * 2，但要减去上次 c 贡献的数量避免重复。

用 last[c] 记录上一次处理 c 时的 total。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)，仅 26 个字母。

class Solution {
    private static final int MOD = 1_000_000_007;

    public int distinctSubseqII(String s) {
        long total = 1;
        long[] last = new long[26];

        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            long next = (total * 2 - last[idx]) % MOD;
            if (next < 0) {
                next += MOD;
            }
            last[idx] = total;
            total = next;
        }

        return (int) ((total - 1 + MOD) % MOD);
    }
}

func distinctSubseqII(s string) int {
	const mod int64 = 1_000_000_007
	total := int64(1)
	last := make([]int64, 26)

	for i := 0; i < len(s); i++ {
		idx := s[i] - 'a'
		next := (total*2 - last[idx]) % mod
		if next < 0 {
			next += mod
		}
		last[idx] = total
		total = next
	}

	ans := (total - 1 + mod) % mod
	return int(ans)
}

相似题目

题目	难度	考察点
115. 不同的子序列	困难	DP
392. 判断子序列	简单	DP
132. 分割回文串 II	困难	DP
1143. 最长公共子序列	中等	DP
516. 最长回文子序列	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/29983138