Number of Substrings With Only 1s - Practice Coding Problems

Number of Substrings With Only 1s - Problem

Math String Medium

Given a binary string s, return the number of substrings with all characters 1's.

Since the answer may be too large, return it modulo 10⁹ + 7.

Example: For string "111", the substrings are: "1" (3 times), "11" (2 times), "111" (1 time), totaling 6 substrings.

Input & Output

Example 1 — Basic Consecutive 1's

$ Input: s = "111"

› Output: 6

💡 Note: Substrings with only 1's: "1" (at positions 0,1,2), "11" (at positions 0-1,1-2), "111" (at position 0-2). Total: 3+2+1 = 6

Example 2 — Mixed String

$ Input: s = "0"

› Output: 0

💡 Note: No substrings contain only 1's, so the count is 0

Example 3 — Multiple Segments

$ Input: s = "1101"

› Output: 3

💡 Note: Segment "11" contributes 2*(2+1)/2 = 3 substrings, segment "1" contributes 1*(1+1)/2 = 1. But wait, let me recalculate: "1" (pos 0), "11" (pos 0-1), "1" (pos 3). Total = 3

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either '0' or '1'

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string with 1's and 0's

Process

Find consecutive segments of 1's

Output

Total count of valid substrings

Key Takeaway

🎯 Key Insight: For n consecutive 1's, there are exactly n×(n+1)/2 valid substrings - use this mathematical property instead of checking every substring individually

Asked in

f Facebook 15 a Amazon 12

The key insight is that for any consecutive sequence of n ones, there are exactly n×(n+1)/2 possible substrings. The optimal approach identifies all consecutive segments and applies this mathematical formula. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula	O(n)	O(1)	Find consecutive segments of 1's and apply formula n*(n+1)/2 for each segment
Brute Force - Check All Substrings	O(n³)	O(1)	Generate every possible substring and check if it contains only 1's

Mathematical Formula — Algorithm Steps

Step 1: Traverse string to find consecutive segments of 1's
Step 2: For each segment of length n, add n*(n+1)/2 to result
Step 3: Return total count modulo 10^9 + 7

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Segments

Identify consecutive runs of 1's

Apply Formula

For each segment of length n: n*(n+1)/2

Sum Results

Add up all segment contributions

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s) {
    const int MOD = 1000000007;
    long long count = 0;
    int consecutiveOnes = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            consecutiveOnes++;
        } else {
            if (consecutiveOnes > 0) {
                count = (count + (long long)consecutiveOnes * (consecutiveOnes + 1) / 2) % MOD;
                consecutiveOnes = 0;
            }
        }
    }
    
    // Handle remaining consecutive 1's at the end
    if (consecutiveOnes > 0) {
        count = (count + (long long)consecutiveOnes * (consecutiveOnes + 1) / 2) % MOD;
    }
    
    return count;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string to identify consecutive segments

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track current segment length and total count

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Formula — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler