Skip to content

2533. Number of Good Binary Strings

  • Time: $O(\texttt{maxLength})$
  • Space: $O(\texttt{maxLength})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  int goodBinaryStrings(int minLength, int maxLength, int oneGroup,
                        int zeroGroup) {
    constexpr int kMod = 1'000'000'007;
    // dp[i] := the number of good binary strings with length i
    vector<int> dp(maxLength + 1);
    dp[0] = 1;  // ""

    for (int i = 0; i <= maxLength; ++i)
      // There are good binary strings with length i, so we can append
      // consecutive 0s or 1s after it.
      if (dp[i] > 0) {
        const int appendZeros = i + zeroGroup;
        if (appendZeros <= maxLength) {
          dp[appendZeros] += dp[i];
          dp[appendZeros] %= kMod;
        }
        const int appendOnes = i + oneGroup;
        if (appendOnes <= maxLength) {
          dp[appendOnes] += dp[i];
          dp[appendOnes] %= kMod;
        }
      }

    return accumulate(dp.begin() + minLength, dp.end(), 0L) % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) {
    final int kMod = 1_000_000_007;
    // dp[i] := the number of good binary strings with length i
    int[] dp = new int[maxLength + 1];
    dp[0] = 1; // ""

    for (int i = 0; i <= maxLength; ++i)
      // There are good binary strings with length i, so we can append
      // consecutive 0s or 1s after it.
      if (dp[i] > 0) {
        final int appendZeros = i + zeroGroup;
        if (appendZeros <= maxLength) {
          dp[appendZeros] += dp[i];
          dp[appendZeros] %= kMod;
        }
        final int appendOnes = i + oneGroup;
        if (appendOnes <= maxLength) {
          dp[appendOnes] += dp[i];
          dp[appendOnes] %= kMod;
        }
      }

    int ans = 0;
    for (int i = minLength; i <= maxLength; ++i) {
      ans += dp[i];
      ans %= kMod;
    }
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def goodBinaryStrings(
      self,
      minLength: int,
      maxLength: int,
      oneGroup: int,
      zeroGroup: int,
  ) -> int:
    kMod = 1_000_000_007
    # dp[i] := the number of good binary strings with length i
    dp = [1] + [0] * maxLength

    for i in range(maxLength + 1):
      # There are good binary strings with length i, so we can append
      # consecutive 0s or 1s after it.
      if dp[i] > 0:
        appendZeros = i + zeroGroup
        if appendZeros <= maxLength:
          dp[appendZeros] += dp[i]
          dp[appendZeros] %= kMod
        appendOnes = i + oneGroup
        if appendOnes <= maxLength:
          dp[appendOnes] += dp[i]
          dp[appendOnes] %= kMod

    return sum(dp[minLength:]) % kMod