Number of Unique Good Subsequences

Hard
1518.

Number of Unique Good Subsequences

Number of Unique Good Subsequences is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

You are given a binary string binary. A subsequence of binary is good if it is non-empty and has no leading zeros — the only good subsequence that starts with 0 is "0" itself.

Return the number of distinct good subsequences of binary, counted as strings (equal strings obtained from different positions count once), modulo 10^9 + 7.

Example 1

Input
binary = "001"
Output
2
Explanation
The good subsequences are `"0"`, `"0"` and `"1"`; as strings that is `"0"` and `"1"`.

Example 2

Input
binary = "110"
Output
5
Explanation
`"0"`, `"1"`, `"10"`, `"11"` and `"110"`.

Example 3

Input
binary = "1011"
Output
7

Constraints

  • 1 <= binary.length <= 10^5
  • binary consists of only '0's and '1's
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} binary
 * @return {number}
 */
var numberOfUniqueGoodSubsequences = function(binary) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Unique Good Subsequences — Problem & Solution

Number of Unique Good Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Number of Unique Good Subsequences is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Strings, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a binary string binary. A subsequence of binary is good if it is non-empty and has no leading zeros — the only good subsequence that starts with 0 is "0" itself.

Return the number of distinct good subsequences of binary, counted as strings (equal strings obtained from different positions count once), modulo 10^9 + 7.

Example 1

Input: binary = "001"
Output: 2
Explanation: The good subsequences are `"0"`, `"0"` and `"1"`; as strings that is `"0"` and `"1"`.

Example 2

Input: binary = "110"
Output: 5
Explanation: `"0"`, `"1"`, `"10"`, `"11"` and `"110"`.

Example 3

Input: binary = "1011"
Output: 7

Constraints

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

Hints for Number of Unique Good Subsequences

  1. Hint 1

    Set "0" aside — it is good exactly when the string contains a 0. Every other good subsequence starts with 1.

  2. Hint 2

    Count distinct subsequences that start with 1, split by their last character: end0 and end1.

  3. Hint 3

    Reading a 1: every distinct one (ending in 0 or 1) can be extended by it, and "1" itself appears — end1 = end0 + end1 + 1. Reading a 0: end0 = end0 + end1. The answer is end0 + end1 + (1 if any 0).

How to solve Number of Unique Good Subsequences

Count distinct strings by their last character. After reading a prefix, let end0 (end1) be the number of distinct subsequences that start with 1 and end with 0 (1). Appending the next character c to every distinct subsequence produces every distinct subsequence ending in c — the new set already contains all the old ones ending in c, so there is no double counting.

Approach

  1. Start with end0 = end1 = 0 and hasZero = 0.
  2. For each character: on 1, set end1 = end0 + end1 + 1 (extend everything, plus the string "1"); on 0, set end0 = end0 + end1 and hasZero = 1 (a 0 cannot start a good subsequence other than "0").
  3. Reduce modulo 10^9 + 7 at each step.
  4. Return end0 + end1 + hasZero modulo 10^9 + 7.

Why it works

Fix a prefix and a string t that starts with 1 and ends with c. If t is a subsequence of the prefix, it can be matched greedily so that its last character uses the latest c; removing that character leaves a distinct subsequence of the earlier part (or the empty string, when t = "1"). So the distinct strings ending in c after reading this c are exactly the previous distinct strings with c appended, plus "1" when c = 1 — which is the update. Strings ending in the other character are unchanged.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • "0" counts once if any 0 exists — it is not built by the recurrence.
  • A 0 never starts a counted subsequence, so the 0-update has no + 1.
  • Counting by positions instead of by strings overcounts heavily ("11" has three subsequences but two distinct strings).

Reference solution

Python

def numberOfUniqueGoodSubsequences(binary: str) -> int:
    MOD = 10 ** 9 + 7
    end0 = end1 = 0
    has_zero = 0
    for ch in binary:
        if ch == '1':
            end1 = (end0 + end1 + 1) % MOD
        else:
            end0 = (end0 + end1) % MOD
            has_zero = 1
    return (end0 + end1 + has_zero) % MOD

Java

public static int numberOfUniqueGoodSubsequences(String binary) {
    final long MOD = 1000000007L;
    long end0 = 0, end1 = 0, hasZero = 0;
    for (int i = 0; i < binary.length(); i++) {
        if (binary.charAt(i) == '1') end1 = (end0 + end1 + 1) % MOD;
        else {
            end0 = (end0 + end1) % MOD;
            hasZero = 1;
        }
    }
    return (int) ((end0 + end1 + hasZero) % MOD);
}

C++

int numberOfUniqueGoodSubsequences(string binary) {
    const long long MOD = 1000000007LL;
    long long end0 = 0, end1 = 0, hasZero = 0;
    for (char ch : binary) {
        if (ch == '1') end1 = (end0 + end1 + 1) % MOD;
        else {
            end0 = (end0 + end1) % MOD;
            hasZero = 1;
        }
    }
    return (int)((end0 + end1 + hasZero) % MOD);
}

JavaScript

var numberOfUniqueGoodSubsequences = function(binary) {
    var MOD = 1000000007, end0 = 0, end1 = 0, hasZero = 0;
    for (var i = 0; i < binary.length; i++) {
        if (binary[i] === '1') end1 = (end0 + end1 + 1) % MOD;
        else {
            end0 = (end0 + end1) % MOD;
            hasZero = 1;
        }
    }
    return (end0 + end1 + hasZero) % MOD;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming