LeetCode 2533: Number of Good Binary Strings

Explanation:

The problem asks us to find the number of good binary strings of length n. A good binary string is a binary string that does not contain any consecutive 0s.

To solve this problem, we can use dynamic programming. We can define a state dp[i][mask] which represents the number of good binary strings of length i where the last three characters are represented by the binary mask. We can then transition to the next state based on the current state.

Algorithm:

1. Initialize a 2D array dp of size n+1 x 8, where n is the length of the binary string and 8 represents all possible combinations of the last 3 characters.
2. Set dp[3][mask] = 1 for all valid masks where the last 3 characters do not contain consecutive 0s.
3. Iterate from i = 4 to n and j = 0 to 7:
   • For each dp[i][j], calculate the number of valid transitions based on the last 3 characters.
   • Update dp[i][j] based on the valid transitions.
4. Return the sum of dp[n][mask] for all valid masks.

Time Complexity: O(n) Space Complexity: O(n) :

class Solution {
    public int numberOfGoodBinaryStrings(int n) {
        long[][] dp = new long[n+1][8];
        for (int mask = 0; mask < 8; mask++) {
            if ((mask & 1) == 0 || (mask & 4) == 0) {
                dp[3][mask] = 1;
            }
        }
        
        for (int i = 4; i <= n; i++) {
            for (int j = 0; j < 8; j++) {
                for (int k = 0; k < 2; k++) {
                    int newMask = ((j << 1) & 7) | k;
                    if ((newMask & 1) == 0 || (newMask & 4) == 0) {
                        dp[i][newMask] += dp[i-1][j];
                        dp[i][newMask] %= 1000000007;
                    }
                }
            }
        }
        
        long ans = 0;
        for (int mask = 0; mask < 8; mask++) {
            ans += dp[n][mask];
            ans %= 1000000007;
        }
        
        return (int) ans;
    }
}