We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Split a String

Number: 1678

Difficulty: Medium

Paid? No

Companies: TikTok, Microsoft

Problem Description

Given a binary string s, split s into 3 non-empty parts s1, s2, s3 such that s = s1 + s2 + s3 and each part contains the same number of ones. Return the number of ways to do so modulo 10^9 + 7.

Key Insights

  • When the total number of ones in s is not divisible by 3, there is no valid split.
  • When the string contains no ones, the answer can be computed using combinatorics, by choosing 2 split points among the (n-1) possible cut positions.
  • Otherwise, compute the number of ones each segment must have (totalOnes/3) and then count the number of valid cut positions between segments by counting consecutive zeros adjacent to the boundaries.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string, since we perform a single pass (or constant number of passes) over s. Space Complexity: O(1) (not including the input string), since we use only a fixed number of variables.

Solution

We first count the total number of ones in s. If totalOnes is 0, then any two cuts chosen among the (n-1) positions yield valid non-empty parts; the result becomes C(n-1, 2).

If totalOnes % 3 != 0, return 0 as the ones cannot be equally distributed.

Otherwise, let onesPerSegment = totalOnes / 3. Traverse the string to locate the positions where the cumulative count of ones equals onesPerSegment (end of the first segment) and 2*onesPerSegment (end of the second segment). Count the number of consecutive positions (i.e. zeros) where a cut can be placed. The product of these two counts gives the total number of ways to split the string.

We then return the answer modulo 10^9+7.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def numWays(self, s: str) -> int:
        mod = 10**9 + 7  # modulo value
        totalOnes = s.count('1')
        n = len(s)
        
        # Case when there are no '1's.
        if totalOnes == 0:
            # Choose 2 cut positions among (n - 1) available positions.
            return ((n - 1) * (n - 2) // 2) % mod
        
        # If totalOnes is not divisible by 3, it's impossible to split equally.
        if totalOnes % 3 != 0:
            return 0
        
        # Each segment should have exactly this many ones.
        onesPerSegment = totalOnes // 3
        firstCutWays = 0  # number of positions for the first cut
        secondCutWays = 0  # number of positions for the second cut
        onesCount = 0
        
        # Find the window for the first cut (end of first segment).
        for char in s:
            if char == '1':
                onesCount += 1
            if onesCount == onesPerSegment:
                firstCutWays += 1
            elif onesCount > onesPerSegment:
                break  # once we exceed, we can stop counting
        
        onesCount = 0
        # Find the window for the second cut (end of second segment).
        for char in s[::-1]:
            if char == '1':
                onesCount += 1
            if onesCount == onesPerSegment:
                secondCutWays += 1
            elif onesCount > onesPerSegment:
                break
        
        return (firstCutWays * secondCutWays) % mod

# Example usage:
# sol = Solution()
# print(sol.numWays("10101"))
← Back to All Questions