In this guide, you will get 940. Distinct Subsequences II LeetCode Solution with the best time and space complexity. The solution to Distinct Subsequences II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Example 1:
Input: s = “abc”
Output: 7
Explanation: The 7 distinct subsequences are “a”, “b”, “c”, “ab”, “ac”, “bc”, and “abc”.
Example 2:
Input: s = “aba”
Output: 6
Explanation: The 6 distinct subsequences are “a”, “b”, “ab”, “aa”, “ba”, and “aba”.
Example 3:
Input: s = “aaa”
Output: 3
Explanation: The 3 distinct subsequences are “a”, “aa” and “aaa”.
Constraints:
1 <= s.length <= 2000
s consists of lowercase English letters.
Complexity Analysis
Time Complexity: O(26n) = O(n)
Space Complexity: O(26) = O(1)
940. Distinct Subsequences II LeetCode Solution in C++
class Solution {
public:
int distinctSubseqII(string s) {
constexpr int kMod = 1'000'000'007;
// endsIn[i] := the number of subsequence that end in ('a' + i)
vector<long> endsIn(26);
for (const char c : s)
endsIn[c - 'a'] = accumulate(endsIn.begin(), endsIn.end(), 1L) % kMod;
return accumulate(endsIn.begin(), endsIn.end(), 0L) % kMod;
}
}; /* code provided by PROGIEZ */
940. Distinct Subsequences II LeetCode Solution in Java
class Solution {
public int distinctSubseqII(String s) {
final int kMod = 1_000_000_007;
// endsIn[i] := the number of subsequence that end in ('a' + i)
long[] endsIn = new long[26];
for (final char c : s.toCharArray())
endsIn[c - 'a'] = (Arrays.stream(endsIn).sum() + 1) % kMod;
return (int) (Arrays.stream(endsIn).sum() % kMod);
}
} // code provided by PROGIEZ
940. Distinct Subsequences II LeetCode Solution in Python
class Solution:
def distinctSubseqII(self, s: str) -> int:
kMod = 1_000_000_007
# endsIn[i] := the number of subsequence that end in ('a' + i)
endsIn = [0] * 26
for c in s:
endsIn[string.ascii_lowercase.index(c)] = (sum(endsIn) + 1) % kMod
return sum(endsIn) % kMod # code by PROGIEZ
