Number Of Unique Good Subsequences - Leetcode Solution

Problem statement:

Given a string s, return the number of unique non-empty subsequences of s that are good.

A subsequence is considered good if there are no repeated characters.

The answer may be too large, return it modulo 109 + 7.

Example 1:

Input: s = "abc" Output: 7 Explanation: The good subsequences of s are ["a", "b", "c", "ab", "ac", "bc", "abc"]. Example 2:

Input: s = "aba" Output: 6 Explanation: The good subsequences of s are ["a", "b", "ab", "ba", "aa", "aba"].

Solution:

This problem can be solved using dynamic programming.

Let dp[i] be the number of unique good subsequences that end at index i in the string s.

To compute dp[i], we need to consider two cases:

Case 1: s[i] is not already included in any of the previous good subsequences.

In this case, we can simply add s[i] to all the good subsequences that ended before index i-1. This will create new good subsequences that end at index i.

Thus, dp[i] += dp[i-1] (since we are simply extending all the previous good subsequences).

Case 2: s[i] is already included in some of the previous good subsequences.

In this case, we cannot simply add s[i] to all the previous good subsequences. We need to remove the previous occurrence(s) of s[i] and then add s[i].

To keep track of the previous occurrences of each character, we can use an array last_occurrence, where last_occurrence[c] stores the index of the last occurrence of character c in the string s.

Let j be the index of the last occurrence of s[i]. We need to remove all the good subsequences that end before index j and include s[i]. These subsequences are already counted in dp[j-1]. So, we need to subtract dp[j-1] from dp[i-1].

Thus, dp[i] += dp[i-1] - dp[j-1].

Finally, we need to update last_occurrence[s[i]] to i.

The answer will be the sum of all dp[i] for i from 0 to n-1, where n is the length of the string s.

The time complexity of this solution is O(n), where n is the length of the string s.

Code in Python:

class Solution: def numberOfUniqueGoodSubsequences(self, s: str) -> int: mod = 10**9 + 7 n = len(s) dp = [0] * n last_occurrence = [-1] * 26 if s[0] != '0': dp[0] = 1 last_occurrence[ord(s[0]) - ord('0')] = 0 for i in range(1, n): dp[i] = dp[i-1] * 2 % mod # case 1 if last_occurrence[ord(s[i]) - ord('0')] != -1: # case 2 j = last_occurrence[ord(s[i]) - ord('0')] dp[i] -= dp[j-1] last_occurrence[ord(s[i]) - ord('0')] = i return (dp[-1] + (s.count('0') == 0)) % mod

Explanation of the code:

We initialize dp array and last_occurrence array. We set dp[0] to 1 if the first character of the string is not '0'. We also store the index of the last occurrence of the first character in last_occurrence array.

Then, we loop through the string from index 1 to n-1 and compute dp[i] using the two cases mentioned above. We also update last_occurrence[s[i]] to i.

Finally, we return the sum of all dp[i] for i from 0 to n-1, and add 1 to the sum if the string does not contain any '0'.

Note that we are using modular arithmetic to avoid integer overflow.

1