Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1987.html

1987. Number of Unique Good Subsequences

Level

Hard

Description

You are given a binary string binary. A subsequence of binary is considered good if it is not empty and has no leading zeros (with the exception of "0").

Find the number of unique good subsequences of binary.

• For example, if binary = "001", then all the good subsequences are ["0", "0", "1"], so the unique good subsequences are "0" and "1". Note that subsequences "00", "01", and "001" are not good because they have leading zeros.

Return the number of unique good subsequences of binary. Since the answer may be very large, return it modulo 10^9 + 7.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: binary = “001”

Output: 2

Explanation: The good subsequences of binary are [“0”, “0”, “1”].

The unique good subsequences are “0” and “1”.

Example 2:

Input: binary = “11”

Output: 2

Explanation: The good subsequences of binary are [“1”, “1”, “11”].

The unique good subsequences are “1” and “11”.

Example 3:

Input: binary = “101”

Output: 5

Explanation: The good subsequences of binary are [“1”, “0”, “1”, “10”, “11”, “101”].

The unique good subsequences are “0”, “1”, “10”, “11”, and “101”.

Constraints:

• 1 <= binary.length <= 10^5
• binary consists of only '0's and '1's.

Solution

Use dynamic programming. Create an array dp of length binary.length() + 1, where dp[i] represents the number of unique good subsequences among the first i characters of binary. Find the first character that is '1' in binary, which is at index startIndex, and set dp[startIndex + 1] = 1. Then calculate the values of dp starting from dp[startIndex + 2] to the end. If there exists character '0' in binary, add 1 to the answer since a single '0' is also a good subsequence. Finally, return the answer.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int numberOfUniqueGoodSubsequences(String binary) {
          final int MODULO = 1000000007;
          int length = binary.length();
          int zeroCount = 0;
          for (int i = 0; i < length; i++) {
              if (binary.charAt(i) == '0') {
                  zeroCount = 1;
                  break;
              }
          }
          int startIndex = -1;
          for (int i = 0; i < length; i++) {
              if (binary.charAt(i) == '1') {
                  startIndex = i;
                  break;
              }
          }
          if (startIndex < 0)
              return 1;
          int[] dp = new int[length + 1];
          dp[startIndex + 1] = 1;
          int[] last = new int[2];
          Arrays.fill(last, -1);
          for (int i = startIndex + 1; i < length; i++) {
              int index = binary.charAt(i) - '0';
              dp[i + 1] = dp[i] * 2 % MODULO;
              if (last[index] >= 0)
                  dp[i + 1] = (dp[i + 1] - dp[last[index]]) % MODULO;
              dp[i + 1] = (dp[i + 1] + MODULO) % MODULO;
              last[index] = i;
          }
          int distinctSubsequences = (dp[length] + zeroCount) % MODULO;
          return distinctSubsequences;
      }
  }
  

• // OJ: https://leetcode.com/problems/number-of-unique-good-subsequences/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      int numberOfUniqueGoodSubsequences(string s) {
          long mod = 1e9 + 7, dup[2] = {}, ans = 1;
          for (char c : s) {
              int prev = ans, zero = dup[0] > 0;
              ans = (2 * ans - dup[c - '0'] - zero + mod) % mod;
              dup[c - '0'] = prev - zero;
          }
          return (ans - 1 + mod) % mod;
      }
  };
  

• class Solution:
      def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
          f = g = 0
          ans = 0
          mod = 10**9 + 7
          for c in binary:
              if c == "0":
                  g = (g + f) % mod
                  ans = 1
              else:
                  f = (f + g + 1) % mod
          ans = (ans + f + g) % mod
          return ans
  
  

• func numberOfUniqueGoodSubsequences(binary string) (ans int) {
  	const mod int = 1e9 + 7
  	f, g := 0, 0
  	for _, c := range binary {
  		if c == '0' {
  			g = (g + f) % mod
  			ans = 1
  		} else {
  			f = (f + g + 1) % mod
  		}
  	}
  	ans = (ans + f + g) % mod
  	return
  }
  

• function numberOfUniqueGoodSubsequences(binary: string): number {
      let [f, g] = [0, 0];
      let ans = 0;
      const mod = 1e9 + 7;
      for (const c of binary) {
          if (c === '0') {
              g = (g + f) % mod;
              ans = 1;
          } else {
              f = (f + g + 1) % mod;
          }
      }
      ans = (ans + f + g) % mod;
      return ans;
  }
  
  

All Problems

All Solutions