- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a binary string s. We have to find the number of substrings with all characters 1's. The answer may be very large so return result mod 10^9 + 7.

So, if the input is like s = "1011010", then the output will be 5 because 1. four times "1" 2. one time "11"

To solve this, we will follow these steps −

m := 10^9+7

result := 0

div := divide the binary string by splitting it using '0'

for each x in div, do

if x is empty, then go for next iteration

result := result + quotient of (size of x *(size of x +1))/2

return result mod m

Let us see the following implementation to get better understanding −

def solve(s): m = 10**9+7 result = 0 for x in s.split('0'): if not x: continue result += (len(x)*(len(x)+1)) // 2 return result % m s = "1011010" print(solve(s))

"1011010"

5

- Related Questions & Answers
- Program to count substrings with all 1s in binary string in Python
- Program to find longest distance of 1s in binary form of a number using Python
- Count Substrings with equal number of 0s, 1s and 2s in C++
- Program to find maximum number of non-overlapping substrings in Python
- Program to find out the number of pairs of equal substrings in Python
- Program to count number of palindromic substrings in Python
- Program to count number of homogenous substrings in Python
- Program to find longest number of 1s after swapping one pair of bits in Python
- Program to find remainder after dividing n number of 1s by m in Python
- Find the Number of Substrings of a String using C++
- Program to find longest subarray of 1s after deleting one element using Python
- Program to find number of different substrings of a string for different queries in Python
- Program to find out number of distinct substrings in a given string in python
- Python program to find N-sized substrings with K distinct characters
- Program to find sum of beauty of all substrings in Python

Advertisements