Number of Ways to Split a String - Practice Coding Problems

Number of Ways to Split a String - Problem

Math String Medium

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 10⁹ + 7.

Input & Output

Example 1 — Equal Distribution

$ Input: s = "10101"

› Output: 4

💡 Note: There are 4 ways to split: "1|010|1", "1|01|01", "10|10|1", "101|0|1". Each gives 1 one per part.

Example 2 — All Zeros

$ Input: s = "0000"

› Output: 3

💡 Note: Any split gives 0 ones in each part. Possible splits: "0|0|00", "0|00|0", "00|0|0".

Example 3 — Impossible Split

$ Input: s = "101"

› Output: 0

💡 Note: 2 ones cannot be split equally among 3 parts (2 ÷ 3 ≠ integer).

Constraints

3 ≤ s.length ≤ 10⁵
s consists only of '0' and '1' characters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Binary string with ones and zeros

Split Requirement

3 non-empty parts with equal number of ones

Count Ways

Return number of valid split combinations

Key Takeaway

🎯 Key Insight: Use math to find valid cut ranges instead of trying all combinations

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to use mathematical analysis instead of brute force. First check if total ones are divisible by 3, then find valid cut position ranges using the positions of '1' characters. Best approach uses mathematical calculation with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Mathematical Approach	O(n)	O(1)	Use math to calculate valid split positions without trying all combinations
Brute Force - Try All Splits	O(n³)	O(1)	Try every possible way to split string into 3 parts and count valid ones

Optimized - Mathematical Approach — Algorithm Steps

Count total ones in string
If not divisible by 3, return 0
Find positions for splitting ones equally
Calculate combinations using position ranges

Visualization

Tap to expand

Step-by-Step Walkthrough

Count & Divide

Count total ones and check if divisible by 3

Find Positions

Locate all '1' positions in the string

Calculate Ranges

Use math to find valid cut position ranges

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int solution(char* s) {
    int n = strlen(s);
    int MOD = 1000000007;
    
    // Count total ones
    int totalOnes = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') totalOnes++;
    }
    
    // Edge case: if no ones, any split works
    if (totalOnes == 0) {
        long long ways = ((long long)(n - 1) * (n - 2) / 2) % MOD;
        return (int)ways;
    }
    
    // If ones not divisible by 3, impossible
    if (totalOnes % 3 != 0) {
        return 0;
    }
    
    int onesPerPart = totalOnes / 3;
    
    // Find positions of ones
    int onePositions[totalOnes];
    int pos = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            onePositions[pos++] = i;
        }
    }
    
    // Find valid ranges for cuts
    int firstThirdEnd = onePositions[onesPerPart - 1];
    int secondThirdStart = onePositions[onesPerPart];
    int secondThirdEnd = onePositions[2 * onesPerPart - 1];
    int thirdThirdStart = onePositions[2 * onesPerPart];
    
    // Count valid positions
    long long firstCutWays = secondThirdStart - firstThirdEnd;
    long long secondCutWays = thirdThirdStart - secondThirdEnd;
    
    return (int)((firstCutWays * secondCutWays) % MOD);
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count ones and find positions

✓ Linear Growth

Space Complexity

O(1)

Only using variables for counts and positions

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Mathematical Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler