Number of Substrings With Only 1s

LeetCode 1636 | Difficulty: Medium

Medium

Problem Description

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^9 + 7.

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.

Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.

Constraints:

- `1 <= s.length <= 10^5`

- `s[i]` is either `'0'` or `'1'`.

Topics: Math, String

---

Approach

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 88 ms)

Metric	Value
Runtime	88 ms
Memory	38.1 MB
Date	2022-01-15

Solution

public class Solution {
    public int NumSub(string s) {
        double result = 0, currsum = 0;
        for(int i=0;i<s.Length;i++)
        {
            if(s[i] == '0')
            {
                
                        
                currsum = 0;
            }
            else
            {
                currsum++;
                result += currsum;
            }
        }
        return (int)(result % ((1e9+7)));
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Count number of 1s in each consecutive-1 group. For a group with n consecutive 1s, the total contribution of it to the final answer is (n + 1) * n // 2.