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 Good Ways to Split a String

Number: 1632

Difficulty: Medium

Paid? No

Companies: Google, Meta

Problem Description

Given a string s, count the number of ways to split the string into two non-empty parts s_left and s_right such that the number of distinct characters in s_left is equal to the number of distinct characters in s_right.

Key Insights

  • Use two passes: one forward to compute the running count of distinct characters from the beginning, and one backward to compute the running count from the end.
  • By precomputing the distinct letter count for every possible split point, the count for each potential split can be quickly compared.
  • A simple iteration through potential split indices lets us count the number of valid splits.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, as we traverse the string twice. Space Complexity: O(n), used for storing the distinct character counts for each prefix and suffix.

Solution

We solve the problem in multiple steps. First, we create an array, leftDistinct, where leftDistinct[i] represents the number of unique characters from the start of the string to index i. We then create a similar array, rightDistinct, where rightDistinct[i] represents the number of unique characters from index i to the end of the string. Finally, we iterate over all valid split positions (from 0 to n-2) and count the splits where leftDistinct[i] equals rightDistinct[i+1]. The main trick here is the efficient counting of distinct characters using a set in a single pass, making the solution linear in time complexity.

Code Solutions

# Python solution
def numSplits(s: str) -> int:
    n = len(s)
    
    # leftDistinct[i] represents the number of unique characters in s[:i+1]
    leftDistinct = [0] * n
    seen_left = set()
    
    for i in range(n):
        seen_left.add(s[i])
        leftDistinct[i] = len(seen_left)
    
    # rightDistinct[i] represents the number of unique characters in s[i:]
    rightDistinct = [0] * n
    seen_right = set()
    
    for i in range(n-1, -1, -1):
        seen_right.add(s[i])
        rightDistinct[i] = len(seen_right)
    
    goodSplits = 0
    # Iterate through all possible split points
    for i in range(n-1):
        if leftDistinct[i] == rightDistinct[i+1]:
            goodSplits += 1
    
    return goodSplits

# For testing
if __name__ == "__main__":
    test_string = "aacaba"
    print(numSplits(test_string))  # Expected output: 2
← Back to All Questions