How do I approach the Distinct Subsequences II problem?

Start by recognizing that this problem requires dynamic programming and state transitions to track subsequences. Handle large outputs with modulo operations.

What is the time complexity of the solution?

The time complexity is O(N), where N is the length of the string.

How do I optimize space for this problem?

You can optimize space by storing only the current and previous states of subsequences, reducing the space complexity to O(N).

What is the significance of modulo 10^9 + 7 in this problem?

The modulo operation ensures that the number of subsequences doesn't overflow the standard integer range, keeping the result manageable.

How does the state transition work in this problem?

At each character, the number of subsequences is updated based on the previous state, adjusting for any duplicates caused by repeating characters.

#940

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

不同的子序列 II

给定一个字符串 s ，计算 s 的不同非空子序列的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余。字符串的子序列是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。例如， "ace" 是 " a b c d e " 的一个子序列，但 "…

字符串动态规划

题目描述

给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。

示例 1：

输入：s = "abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

示例 2：

输入：s = "aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

示例 3：

输入：s = "aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成

lightbulb

解题思路

方法一：动态规划

定义 $dp[i]$ 表示以 $s[i]$ 结尾的不同子序列的个数。由于 $s$ 中只包含小写字母，因此我们可以直接创建一个长度为 $26$ 的数组。初始时 $dp$ 所有元素均为 $0$ 。答案为 $\sum_{i=0}^{25}dp[i]$ 。

遍历字符串 $s$ ，对于每个位置的字符 $s[i]$ ，我们需要更新以 $s[i]$ 结尾的不同子序列的个数，此时 $dp[i]=\sum_{j=0}^{25}dp[j]+1$ 。其中 $\sum_{j=0}^{25}dp[j]$ 是此前我们已经计算出所有不同子序列的个数，而 $+1$ 是指 $s[i]$ 本身也可以作为一个子序列。

最后，我们需要对 $dp$ 中的所有元素求和，再对 $10^9+7$ 取余，即为答案。

时间复杂度 $O(n\times C)$ ，其中 $n$ 是字符串 $s$ 的长度，而 $C$ 是字符集的大小，本题中 $C=26$ 。空间复杂度 $O(C)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod = 10**9 + 7
        n = len(s)
        dp = [[0] * 26 for _ in range(n + 1)]
        for i, c in enumerate(s, 1):
            k = ord(c) - ord('a')
            for j in range(26):
                if j == k:
                    dp[i][j] = sum(dp[i - 1]) % mod + 1
                else:
                    dp[i][j] = dp[i - 1][j]
        return sum(dp[-1]) % mod

speed

复杂度分析

指标	值
时间	O(N)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of dynamic programming with state transitions.
question_mark
Candidate efficiently handles modulo operation and optimizes for large outputs.
question_mark
Candidate is able to reduce space complexity while maintaining the correctness of the solution.

warning

常见陷阱

外企场景

error
Mismanaging state transitions or failing to correctly account for previously seen characters.
error
Overcomplicating the problem by using unnecessary extra space for subsequences.
error
Failing to apply the modulo operation correctly and causing overflow.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider an extension where the string contains multiple distinct characters and the subsequences are constrained by specific conditions.
arrow_right_alt
A variant where the input string is limited to a smaller set of characters, altering the number of possible subsequences.
arrow_right_alt
Another variant could involve counting subsequences that follow specific patterns or orderings within the string.

help

常见问题

外企场景

继续练习

#943 最短超级串 #926 将字符串翻转到单调递增 #960 删列造序 III