1573. Number of Ways to Split a String

Time: O(n)

Space: O(1)

Approach

Count ones; if not divisible by 3 return 0; choose 2 split points from gaps between groups.

Key Techniques

String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.

Math

Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.

1573.cs

// Approach: Count ones; if not divisible by 3 return 0; choose 2 split points from gaps between groups.
// Time: O(n) Space: O(1)

public class Solution
{
    public int NumWays(string s)
    {
        const int kMod = 1_000_000_007;
        int ones = s.Count(c => c == '1');
        if (ones % 3 != 0)
            return 0;
        if (ones == 0)
        {
            long n = s.Length;
            return (int)((n - 1) * (n - 2) / 2 % kMod);
        }

        int s1End = -1;
        int s2Start = -1;
        int s2End = -1;
        int s3Start = -1;
        int onesSoFar = 0;

        for (int i = 0; i < s.Length; ++i)
        {
            if (s[i] == '1')
                ++onesSoFar;
            if (s1End == -1 && onesSoFar == ones / 3)
                s1End = i;
            else if (s2Start == -1 && onesSoFar == ones / 3 + 1)
                s2Start = i;
            if (s2End == -1 && onesSoFar == ones / 3 * 2)
                s2End = i;
            else if (s3Start == -1 && onesSoFar == ones / 3 * 2 + 1)
                s3Start = i;
        }

        return (int)((long)(s2Start - s1End) * (s3Start - s2End) % kMod);
    }
}

Was this solution helpful?