- 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 can split s into 3 non-empty strings s1, s2, s3 such that (s1 concatenate s2 concatenate s3 = s). We have to find the number of ways s can be split such that the number of characters '1' is the same in s1, s2, and s3. The answer may be very large so return answer mod 10^9+7.

So, if the input is like s = "11101011", then the output will be 2 because we can split them like "11 | 1010 | 11" and "11 | 101 | 011".

To solve this, we will follow these steps:

- count := count number of 1s in s
- m := 10^9 + 7
- ans := an array of size 2 and fill with 0
- if count mod 3 is not same as 0, then
- return 0

- otherwise when count is same as 0, then
- return (nCr of where n is size of s -1 and r is 2) mod m

- left := 0
- right := size of s - 1
- cum_s := 0, cum_e := 0
- while cum_s <= quotient of count/3 or cum_e <= quotient of count/3, do
- if s[left] is same as "1", then
- cum_s := cum_s + 1

- if s[right] is same as "1", then
- cum_e := cum_e + 1

- if cum_s is same as quotient of count/3, then
- ans[0] := ans[0] + 1

- if cum_e is same as quotient of count/3, then
- ans[1] := ans[1] + 1

- left := left + 1
- right := right - 1

- if s[left] is same as "1", then
- return (ans[0]*ans[1]) mod m

Let us see the following implementation to get better understanding:

def solve(s): count = s.count("1") m = 10**9 + 7 ans = [0, 0] if count % 3 != 0: return 0 elif count == 0: return comb(len(s)-1,2) % m left = 0 right = len(s)-1 cum_s = 0 cum_e = 0 while(cum_s <= count//3 or cum_e <= count//3): if s[left] == "1": cum_s+=1 if s[right] == "1": cum_e+=1 if cum_s == count//3: ans[0]+=1 if cum_e == count//3: ans[1]+=1 left += 1 right -= 1 return (ans[0]*ans[1]) % m s = "11101011" print(solve(s))

"11101011"

2

- Related Questions & Answers
- Program to find number of good ways to split a string using Python
- Program to find number of ways we can split a palindrome in python
- Program to find number of ways to split array into three subarrays in Python
- Program to find number of ways to form a target string given a dictionary in Python
- Program to find split a string into the max number of unique substrings in Python
- Program to find number of ways we can decode a message in Python
- Python program to split and join a string?
- Find length of a string in python (3 ways)
- Program to find number of different integers in a string using Python
- Program to find number of ways where square of number is equal to product of two numbers in Python
- Program to find number of ways we can arrange symbols to get target in Python?
- Program to find number of ways we can concatenate words to make palindromes in Python
- How to split a string in Python
- Program to find minimum number of monotonous string groups in Python
- Program to find ways to make a fair array in Python

Advertisements