1513. Number of Substrings With Only 1s
Approach
Count consecutive 1s ending at each position; each run of length k contributes k new substrings.
Key Techniques
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.
// Approach: Count consecutive 1s ending at each position; each run of length k contributes k new substrings.
// Time: O(n) Space: O(1)
public class Solution
{
public int NumSub(string s)
{
// Define modulo constant to prevent integer overflow
const int MODULO = (int)1e9 + 7;
// Total count of valid substrings
int totalCount = 0;
// Current consecutive '1's count ending at current position
int consecutiveOnes = 0;
// Iterate through each character in the string
for (int i = 0; i < s.Length; i++)
{
// If current character is '1', increment consecutive count
// Otherwise, reset consecutive count to 0
if (s[i] == '1')
consecutiveOnes++;
else
consecutiveOnes = 0;
// Add current consecutive count to total
// This represents all substrings of '1's ending at position i
totalCount = (totalCount + consecutiveOnes) % MODULO;
}
return totalCount;
}
}