String Count
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.dynamic_programming;
import java.util.*;
/ * Problem: String Count * Group: 11. Dynamic Programming */ / * ============================================================================================ * PROBLEM: String Count (Binary Strings without Consecutive 1s) * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given an integer A, find the total number of binary strings of length A that do NOT * contain consecutive 1s. * Return the result modulo 10^9 + 7. * * Example: * A = 2 -> "00", "01", "10" (Count: 3). "11" is invalid. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * We can define the state based on the last character placed. * Let dp[i][0] = Number of valid strings of length 'i' ending in '0'. * Let dp[i][1] = Number of valid strings of length 'i' ending in '1'. * * Transitions: * 1. If we place a '0' at position i: * The previous character (at i-1) could have been '0' OR '1'. * dp[i][0] = dp[i-1][0] + dp[i-1][1] * * 2. If we place a '1' at position i: * The previous character MUST be '0' (to avoid "11"). * dp[i][1] = dp[i-1][0] * * Total Count for length i = dp[i][0] + dp[i][1]. * * Optimization (Fibonacci Observation): * Let Total[i] be the total count for length i. * Total[i] = dp[i][0] + dp[i][1] * = (dp[i-1][0] + dp[i-1][1]) + (dp[i-1][0]) * = Total[i-1] + (Total[i-2]) <-- Since dp[i-1][0] is exactly Total[i-2] appended with '0'. * * Resulting Sequence: * Length 1: 2 ("0", "1") * Length 2: 3 ("00", "01", "10") * Length 3: 5 * Length 4: 8 * This is the Fibonacci sequence starting from 2, 3... * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= A <= 10^5 * Modulo: 10^9 + 7 * * Time Complexity: * O(A) - Linear iteration. * * Space Complexity: * O(1) - We only need two variables to store the previous counts. * * ============================================================================================ */ public class StringCount { public int solve(int A) { // TODO: Implement solution return 0; } }