Distinct Subsequences Ii - Leetcode Solution

Problem Statement:

Given a string s, return the number of distinct non-empty subsequences of s modulo 109 + 7.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A distinct subsequence is a subsequence that appears different in s.

Constraints:

1 <= s.length <= 2000 s consists of lowercase English letters.

Solution:

Approach:

The problem states that we need to count the number of distinct subsequences of the given string.

First, we create a count array to count the frequency of each character in the input string.

Next, we initialize an array dp, such that dp[i] represents the number of distinct subsequences ending at index i of the input string s.

We initialize dp[0] = 1, as the empty string is also a subsequence of the given input string.

Now, for each character in s[i], we need to find the number of distinct subsequences that can be formed with this character. To do this, we first subtract the number of subsequences formed by the same character before index i. We do this because we need to ensure that the current character is forming a 'distinct' subsequence.

For example, if s = "ababa" and we are processing the 4th character 'b'. We need to subtract the number of distinct subsequences formed by 'b' before the 4th index. This is because if we don't subtract, we will be counting subsequences like 'b', 'bb', 'bbb' again.

Therefore, we subtract dp[j-1], where j is the index of the last occurrence of s[i], before the current index i.

Finally, we update the value of dp[i] by adding the result to the previous value of dp[i-1].

In other words, the number of distinct subsequences ending at index i is the sum of the number of distinct subsequences ending at index i-1 and the number of distinct subsequences that can be formed with the current character.

We return the final answer by taking the modulo 10^9 + 7.

Code:

class Solution { public int distinctSubseqII(String s) { int n = s.length(); int mod = (int)1e9 + 7; int[] dp = new int[n]; int[] count = new int[26]; dp[0] = 1; count[s.charAt(0) - 'a']++; for(int i = 1; i < n; i++){ int index = s.charAt(i) - 'a'; // the number of subsequences formed with this character // is the number of distinct subsequences formed by all the // characters before this one plus the current character itself. dp[i] = (dp[i - 1] * 2) % mod; // subtracting the number of subsequences formed with the same // character before index i dp[i] = (dp[i] - dp[count[index] - 1] + mod) % mod; count[index] = i; } return dp[n - 1]; } }

Time Complexity: O(n)

Space Complexity: O(n)

1