Scale Engineer

Number of Ways to Split a String

Med
#1447Time: O(N^3), where N is the length of the string. The two nested loops run in O(N^2), and inside the loops, creating and counting ones in substrings takes O(N) time.Space: O(N), where N is the length of the string. This is due to the creation of substrings in each iteration.
Patterns
Math
Data structures
String

Prompt

Given a binary string s, you can split s into 3 non-empty strings s1, s2, and s3 where s1 + s2 + s3 = s.

Return the number of ways s can be split such that the number of ones is the same in s1, s2, and s3. Since the answer may be too large, return it modulo 109 + 7.

 

Example 1:

Input: s = "10101"
Output: 4
Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters '1'.
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"

Example 2:

Input: s = "1001"
Output: 0

Example 3:

Input: s = "0000"
Output: 3
Explanation: There are three ways to split s in 3 parts.
"0|0|00"
"0|00|0"
"00|0|0"

 

Constraints:

  • 3 <= s.length <= 105
  • s[i] is either '0' or '1'.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach exhaustively checks every possible way to split the string into three non-empty parts. It uses nested loops to define the two cut points and then, for each split, counts the number of '1's in each of the three resulting substrings to see if they are equal.

Algorithm

  • Initialize a counter ways to 0.
  • Use a nested loop structure to iterate through all possible pairs of cut points. The outer loop for the first cut i runs from 0 to n-3, and the inner loop for the second cut j runs from i+1 to n-2.
  • For each pair (i, j), split the string s into three substrings: s1 = s.substring(0, i + 1), s2 = s.substring(i + 1, j + 1), and s3 = s.substring(j + 1).
  • Create a helper function countOnes to count the number of '1's in a string.
  • Call countOnes for s1, s2, and s3.
  • If the counts are equal, increment the ways counter.
  • After the loops complete, return ways.

Walkthrough

The algorithm iterates through all possible pairs of cut points (i, j). The first cut is after index i and the second after index j. The loops ensure that 0 <= i < j < n-1, which guarantees three non-empty substrings: s1 = s[0...i], s2 = s[i+1...j], and s3 = s[j+1...n-1]. For each such split, we manually count the '1's in s1, s2, and s3. If the counts are equal, we increment a result counter. This method is simple to understand but highly inefficient due to the repeated counting within the nested loops.

class Solution {    public int numWays(String s) {        int n = s.length();        long ways = 0;        int MOD = 1_000_000_007;         // i is the end index of s1        for (int i = 0; i < n - 2; i++) {            // j is the end index of s2            for (int j = i + 1; j < n - 1; j++) {                String s1 = s.substring(0, i + 1);                String s2 = s.substring(i + 1, j + 1);                String s3 = s.substring(j + 1);                 int ones1 = countOnes(s1);                int ones2 = countOnes(s2);                int ones3 = countOnes(s3);                 if (ones1 == ones2 && ones2 == ones3) {                    ways++;                }            }        }        return (int) (ways % MOD);    }     private int countOnes(String str) {        int count = 0;        for (char c : str.toCharArray()) {            if (c == '1') {                count++;            }        }        return count;    }}

Complexity

Time

O(N^3), where N is the length of the string. The two nested loops run in O(N^2), and inside the loops, creating and counting ones in substrings takes O(N) time.

Space

O(N), where N is the length of the string. This is due to the creation of substrings in each iteration.

Trade-offs

Pros

  • Simple to conceptualize and implement.

Cons

  • Extremely inefficient due to its O(N^3) time complexity.

  • Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

Solutions

class Solution {private  String s;public  int numWays(String s) {    this.s = s;    int cnt = 0;    int n = s.length();    for (int i = 0; i < n; ++i) {      if (s.charAt(i) == '1') {        ++cnt;      }    }    int m = cnt % 3;    if (m != 0) {      return 0;    }    final int mod = (int)1 e9 + 7;    if (cnt == 0) {      return (int)(((n - 1L) * (n - 2) / 2) % mod);    }    cnt /= 3;    long i1 = find(cnt), i2 = find(cnt + 1);    long j1 = find(cnt * 2), j2 = find(cnt * 2 + 1);    return (int)((i2 - i1) * (j2 - j1) % mod);  }private  int find(int x) {    int t = 0;    for (int i = 0;; ++i) {      t += s.charAt(i) == '1' ? 1 : 0;      if (t == x) {        return i;      }    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem