Number of Substrings With Only 1s

Medium
1218.

Number of Substrings With Only 1s

Number of Substrings With Only 1s is a medium coding problem on strings and math, asked in Amazon and Google interviews.

Given a binary string s, return the number of its substrings that consist only of 1 characters. Substrings at different positions count separately even when they are equal.

The answer may be large, so return it modulo 10^9 + 7.

Example 1

Input
s = "1101111"
Output
13
Explanation
The run `11` has 3 such substrings and the run `1111` has 10.

Example 2

Input
s = "000"
Output
0

Example 3

Input
s = "1111111111"
Output
55

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is '0' or '1'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var numSub = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Substrings With Only 1s — Problem & Solution

Number of Substrings With Only 1s solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Substrings With Only 1s is a medium coding problem on strings and math, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Math
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a binary string s, return the number of its substrings that consist only of 1 characters. Substrings at different positions count separately even when they are equal.

The answer may be large, so return it modulo 10^9 + 7.

Example 1

Input: s = "1101111"
Output: 13
Explanation: The run `11` has 3 such substrings and the run `1111` has 10.

Example 2

Input: s = "000"
Output: 0

Example 3

Input: s = "1111111111"
Output: 55

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is '0' or '1'

Hints for Number of Substrings With Only 1s

  1. Hint 1

    Every all-ones substring lies inside one maximal run of ones.

  2. Hint 2

    A run of length L contains L·(L+1)/2 all-ones substrings.

  3. Hint 3

    Equivalently, scan once: the number of all-ones substrings ending at position i is the current run length; add it up modulo 10^9 + 7.

How to solve Number of Substrings With Only 1s

Count the all-ones substrings by their right end: those ending at i number exactly the length of the run of ones ending at i.

Approach

  1. Keep run, the number of consecutive 1s ending at the current index (reset to 0 on a 0).
  2. At each 1, increment run and add it to the answer, reducing modulo 10^9 + 7.
  3. Return the answer.

Why it works

An all-ones substring ending at i starts somewhere inside the run that ends at i, and every such start works, so there are run of them; summing over all right ends counts every substring once. Summed over a whole run this is 1 + 2 + … + L = L(L+1)/2. The answer before reduction can reach about 5·10^9, beyond 32 bits, but each step adds at most 10^5 to a value below 10^9 + 7, so reducing as you go keeps every intermediate under 2^31.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Computing L·(L+1)/2 in 32-bit arithmetic overflows for L near 10^5.
  • Forgetting the modulus: a string of 10^5 ones has 5 000 050 000 such substrings.
  • Resetting the run on a 0 but forgetting the final run at the end of the string (in the run-length formulation).

Reference solution

Python

def numSub(s: str) -> int:
    total = 0
    for run in s.split("0"):
        n = len(run)
        total += n * (n + 1) // 2
    return total % 1000000007

Java

public static int numSub(String s) {
    final int MOD = 1000000007;
    int ans = 0, run = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '1') {
            run++;
            ans = (ans + run) % MOD;
        } else {
            run = 0;
        }
    }
    return ans;
}

C++

int numSub(string s) {
    const int MOD = 1000000007;
    int ans = 0, run = 0;
    for (char c : s) {
        if (c == '1') {
            run++;
            ans = (ans + run) % MOD;
        } else {
            run = 0;
        }
    }
    return ans;
}

JavaScript

var numSub = function(s) {
    var MOD = 1000000007, ans = 0, run = 0;
    for (var i = 0; i < s.length; i++) {
        if (s.charCodeAt(i) === 49) {
            run++;
            ans = (ans + run) % MOD;
        } else {
            run = 0;
        }
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings