k Times Appearing Adjacent Two 1's

Problem Overview

Count binary strings of length n where the substring "11" occurs exactly k times.

Intuition

Count binary strings of length n where the substring "11" occurs exactly k times. Track length, the last bit, and how many "11" pairs have been formed. Appending 0 never creates a pair; appending 1 after 0 does not; appending 1 after 1 increments the pair count by one.

Algorithm

1dp[i][last][j] = strings of length i, ending in last (0 or 1), with j adjacent-11 counts.
2Base length 1: dp[1][0][0] = dp[1][1][0] = 1.
3Extend each state to length i + 1 with the three transitions above (cap j at k).
4Answer = dp[n][0][k] + dp[n][1][k] modulo 10⁹ + 7.

Example Walkthrough

Input: n = 3, k = 1

1. Strings like 011, 110, 111 have exactly one "11" overlap.
2. 011 has one pair at positions 1–2; count valid strings via DP.

Output: number of valid binary strings mod 10⁹ + 7

Common Pitfalls

• Only consecutive 1s count — "101" has zero pairs.
• When j = k, do not transition by appending 1 after 1.
• Sum both ending bits 0 and 1 at the final length.

k Times Appearing Adjacent Two 1's.java

Java

// Approach: DP on length i, last bit (0/1), and count of adjacent "11" substrings so far.
// Append 0: no new pair. Append 1 after 0: no new pair. Append 1 after 1: increment pair count.
// Time: O(n * k) Space: O(n * k)

class Solution {

    public int countStrings(int n, int k) {
        int[][][] dp = new int[n + 1][2][k + 1];
        dp[1][0][0] = dp[1][1][0] = 1;
        int mod = 1000000007;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i + 1][0][j] = (dp[i + 1][0][j] + dp[i][0][j]) % mod;
                dp[i + 1][1][j] = (dp[i + 1][1][j] + dp[i][0][j]) % mod;
                dp[i + 1][0][j] = (dp[i + 1][0][j] + dp[i][1][j]) % mod;
                if (j + 1 <= k) {
                    dp[i + 1][1][j + 1] = (dp[i + 1][1][j + 1] + dp[i][1][j]) % mod;
                }
            }
        }
        
        return (dp[n][0][k] + dp[n][1][k]) % mod;
    }
}

Was this solution helpful?