# Number of Substrings With Only 1s
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-substrings-with-only-1s)
Canonical: https://scaleengineer.com/dsa/problems/number-of-substrings-with-only-1s
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String
---
## Problem
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 `109 + 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 <= 105`
* `s[i]` is either `'0'` or `'1'`.

# Approaches
## Brute Force with Nested Loops
This approach involves generating all possible substrings of the input string and checking each one to see if it consists solely of '1's. We use two nested loops to define the start and end points of each substring.
**Time:** O(N^2), where N is the length of the string `s`. In the worst-case scenario (a string of all '1's), the inner loop runs approximately N times for each iteration of the outer loop. · **Space:** O(1), as we only use a few variables to store the count and loop indices, regardless of the input size.
**Pros:** Easy to understand and implement as it directly translates the problem definition.
**Cons:** Highly inefficient and will result in a 'Time Limit Exceeded' error for the given constraints (N up to 10^5).
### Explanation
The algorithm iterates through every possible starting position `i` of a substring. For each starting position, it iterates through every possible ending position `j`. If the character at the starting position `s[i]` is '1', we then check subsequent characters. As long as we encounter '1's, each character `s[j]` helps form a new valid substring `s[i...j]`. We increment our total count for each such valid substring. If we encounter a '0', we know that no further substrings starting at `i` can be valid, so we break the inner loop and move to the next starting position `i+1`.

```java
class Solution {
    public int numSub(String s) {
        long count = 0;
        int n = s.length();
        int mod = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                for (int j = i; j < n; j++) {
                    if (s.charAt(j) == '1') {
                        count++;
                    } else {
                        break; // End of a sequence of 1s
                    }
                }
            }
        }

        return (int) (count % mod);
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use an outer loop to iterate through the string with index `i` from 0 to `n-1`, representing the start of a potential substring.
- If `s.charAt(i)` is '0', continue to the next starting position.
- If `s.charAt(i)` is '1', start an inner loop with index `j` from `i` to `n-1`.
- Inside the inner loop, if `s.charAt(j)` is '1', it means the substring from `i` to `j` is valid. Increment `count`.
- If `s.charAt(j)` is '0', break the inner loop as no more valid substrings can be formed starting from `i`.
- After the loops complete, return `count` modulo 10^9 + 7.

## Optimal Single Pass Approach
A more efficient approach is to iterate through the string once and count the lengths of contiguous blocks of '1's. For a block of `k` consecutive '1's, the number of substrings it can form is the sum of integers from 1 to `k`, which is `k * (k + 1) / 2`. However, a simpler way to achieve the same result is to add the length of the current consecutive block of '1's to the total count at each step.
**Time:** O(N), where N is the length of the string `s`. We perform a single pass through the string. · **Space:** O(1), as we only use a constant amount of extra space for our counter variables.
**Pros:** Extremely efficient and optimal in terms of time and space complexity.; Handles large inputs within the time limits.
**Cons:** The logic of adding `currentCount` at each step might require a moment of thought to understand its correctness compared to the more direct `k*(k+1)/2` formula.
### Explanation
This method avoids nested loops by using a single pass. We maintain a variable, `currentCount`, to track the length of the current contiguous sequence of '1's. We iterate through the string. If the current character is '1', we increment `currentCount`. If it's a '0', the sequence is broken, so we reset `currentCount` to 0. At each step of the iteration, we add the value of `currentCount` to our `totalCount`. This works because a sequence of `k` ones adds `k` new substrings ending at the current position. For example, for '111', the counts added are 1 (for '1'), then 2 (for '1', '11' ending at the second '1'), then 3 (for '1', '11', '111' ending at the third '1'), summing to 1+2+3=6. All calculations are done modulo 10^9 + 7 to prevent overflow.

```java
class Solution {
    public int numSub(String s) {
        long totalCount = 0;
        long currentCount = 0;
        int mod = 1_000_000_007;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                currentCount++;
            } else {
                currentCount = 0;
            }
            totalCount = (totalCount + currentCount) % mod;
        }

        return (int) totalCount;
    }
}
```
### Algorithm
- Initialize `totalCount` (for the final result) and `currentCount` (for the length of the current block of '1's) to 0.
- Define the modulus `mod = 10^9 + 7`.
- Iterate through the string `s` from left to right.
- If the current character is '1', increment `currentCount`.
- If the current character is '0', reset `currentCount` to 0, as the contiguous block of '1's is broken.
- In every iteration, add the current value of `currentCount` to `totalCount`.
- Perform the addition modulo `mod` to prevent overflow: `totalCount = (totalCount + currentCount) % mod`.
- After the loop, `totalCount` will hold the final result.

# Solutions
### CPP

```cpp
class Solution {
public:
  int numSub(string s) {
    int ans = 0, cnt = 0;
    const int mod = 1e9 + 7;
    for (char &c : s) {
      cnt = c == '1' ? cnt + 1 : 0;
      ans = (ans + cnt) % mod;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numSub(self, s: str) -> int: ans = cnt = 0 for c in s: if c == "1": cnt += 1 else: cnt = 0 ans += cnt return ans % (10 ** 9 + 7)

```

### Java

```java
class Solution {
public
  int numSub(String s) {
    final int mod = (int)1 e9 + 7;
    int ans = 0, cnt = 0;
    for (int i = 0; i < s.length(); ++i) {
      cnt = s.charAt(i) == '1' ? cnt + 1 : 0;
      ans = (ans + cnt) % mod;
    }
    return ans;
  }
}

```