How do you solve Number of Substrings With Only 1s on LeetCode?

Number of Substrings With Only 1s (LeetCode #1513) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Count groups of consecutive '1's to simplify the problem.

What is the brute force solution for Number of Substrings With Only 1s?

The brute force approach for Number of Substrings With Only 1s is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible substrings of the binary string and counting those that consist solely of '1's. While straightforward, this method can be inefficient for long strings due to its quadratic time complexity. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Number of Substrings With Only 1s?

Number of Substrings With Only 1s uses the following concepts: Math, String. The recommended patterns to study are: Two Pointers, Sliding Window.

What are the interview tips for Number of Substrings With Only 1s?

Always consider edge cases, such as strings with no '1's or all '1's. Explain your thought process clearly while coding, as it helps interviewers understand your approach. Practice writing code without an IDE to simulate the interview environment.

What are common mistakes when solving Number of Substrings With Only 1s?

Failing to reset the count of consecutive '1's when encountering a '0'. Not applying the modulo operation to the final count, leading to overflow.

#1513

Number of Substrings With Only 1s

Medium

MathStringTwo PointersSliding Window

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach counts consecutive '1's and calculates the number of valid substrings directly from these counts. This is efficient because it avoids generating all substrings and only focuses on groups of '1's.

⚙️

Algorithm

5 steps

1Step 1: Initialize a count variable to zero and a variable to track the length of consecutive '1's.
2Step 2: Iterate through the string, counting consecutive '1's.
3Step 3: When a '0' is encountered or the end of the string is reached, calculate the number of substrings from the count of '1's using the formula (n * (n + 1)) / 2 and add to the total count.
4Step 4: Reset the count of consecutive '1's when a '0' is encountered.
5Step 5: Return the total count modulo 10^9 + 7.

solution.py14 lines

1# Full working Python code
2
3def countSubstrings(s):
4    count = 0
5    consecutive_ones = 0
6    MOD = 10**9 + 7
7    for char in s:
8        if char == '1':
9            consecutive_ones += 1
10        else:
11            count += (consecutive_ones * (consecutive_ones + 1)) // 2
12            consecutive_ones = 0
13    count += (consecutive_ones * (consecutive_ones + 1)) // 2
14    return count % MOD

ℹ

Complexity note: This complexity is linear because we traverse the string once, counting consecutive '1's and calculating the total substrings in constant time.

1Count groups of consecutive '1's to simplify the problem.
2Use the formula (n * (n + 1)) / 2 to calculate contributions from each group.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.