Number of Substrings With Only 1s

Number of Substrings With Only 1s

What is this problem about?

The Number of Substrings With Only 1s problem gives you a binary string and asks you to count all substrings that consist entirely of '1's. This is equivalent to finding all runs of consecutive '1's and summing the triangular numbers for each run. This coding problem tests the "count substrings in a run" mathematical insight.

Why is this asked in interviews?

Google asks this medium problem to test whether candidates recognize the incremental run-length counting pattern. For a run of L consecutive '1's, the number of all-1 substrings is L*(L+1)/2. The math and string interview pattern is applied with the same incremental contribution technique used in "smooth descent periods."

Algorithmic pattern used

Run tracking with incremental count. For each position i, track the length of the current all-1 run ending at i. If s[i]='1', run = prev_run + 1. If s[i]='0', run = 0. Add run to the total count. This incrementally counts all-1 substrings ending at position i as run (since any starting point within the current run forms a valid substring). Apply mod 10^9+7.

Example explanation

s = "0111". Process:

• i=0, '0': run=0. Total=0.
• i=1, '1': run=1. Total=1.
• i=2, '1': run=2. Total=3. (Substrings: "1" at i=1, "1" at i=2, "11").
• i=3, '1': run=3. Total=6. (New: "1" at i=3, "11" ending here, "111"). Answer = 6 = 1+2+3 = run for length 3 = 3*4/2 = 6. ✓

Common mistakes candidates make

• Computing L*(L+1)/2 for each run separately (correct but more complex than incremental approach).
• Not resetting run to 0 when a '0' is encountered.
• Not applying modulo at each step (overflow for long strings of 1s).
• Off-by-one: run starts at 1 for a '1', not 0.

Interview preparation tip

The incremental run count approach — add current run length to total at each step — is cleaner than finding all runs and computing formulas. It's a universal pattern for "count subarrays/substrings of a contiguous type" problems. Practice similar problems: "count subarrays with all equal elements," "number of arithmetic subarray runs." The incremental addition naturally computes L*(L+1)/2 for a run of length L.