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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Good Ways to Split a String

Difficulty: Medium

Problem Description

You are given a string s. A split is called good if you can split s into two non-empty strings s_left and s_right where their concatenation is equal to s (i.e., s_left + s_right = s) and the number of distinct letters in s_left and s_right is the same. Return the number of good splits you can make in s.

Key Insights

  • A split is good if the number of distinct characters in both parts of the split is equal.
  • We can keep track of the number of distinct characters in both the left and right parts as we iterate through the string.
  • Using hash tables (or dictionaries) can help efficiently count and compare the distinct characters.
  • The problem can be solved in a single pass through the string by maintaining running counts of distinct characters.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), since we only store counts of 26 lowercase letters.

Solution

We can use two hash tables (or dictionaries): one to count characters in the left part of the string and the other to count characters in the right part. We initialize the right part with all characters from the string and progressively move one character from the right to the left while updating our counts. Whenever the counts of distinct characters match, we have found a good split.

Code Solutions

def numSplits(s: str) -> int:
    left_count = {}
    right_count = {}
    
    # Initialize right_count with all characters in the string
    for char in s:
        right_count[char] = right_count.get(char, 0) + 1
        
    good_splits = 0
    left_distinct = 0
    right_distinct = len(right_count)
    
    # Iterate through the string and count good splits
    for i in range(len(s) - 1):  # We stop before the last character to ensure non-empty strings
        char = s[i]
        
        # Move character from right to left
        # Update left_count
        if char in left_count:
            left_count[char] += 1
        else:
            left_count[char] = 1
            left_distinct += 1
        
        # Update right_count
        right_count[char] -= 1
        if right_count[char] == 0:
            del right_count[char]
            right_distinct -= 1
            
        # Check for good split
        if left_distinct == right_distinct:
            good_splits += 1
            
    return good_splits
← Back to All Questions