Problem Description

You have a string s that you need to split into two parts. The split is considered "good" when:

1. You divide the string into two non-empty parts: s_left and s_right
2. When concatenated, they form the original string: s_left + s_right = s
3. The number of distinct letters in s_left equals the number of distinct letters in s_right

Your task is to count how many different positions in the string allow for a "good" split.

For example, if s = "aacaba":

• Splitting at position 1: "a" and "acaba" → 1 distinct letter vs 3 distinct letters (not good)
• Splitting at position 2: "aa" and "caba" → 1 distinct letter vs 3 distinct letters (not good)
• Splitting at position 3: "aac" and "aba" → 2 distinct letters vs 2 distinct letters (good!)
• Splitting at position 4: "aaca" and "ba" → 2 distinct letters vs 2 distinct letters (good!)
• Splitting at position 5: "aacab" and "a" → 3 distinct letters vs 1 distinct letter (not good)

The solution uses a two-pointer approach with a counter. It maintains:

• cnt: A counter tracking distinct characters and their frequencies in the right part (initially the entire string)
• vis: A set tracking distinct characters in the left part (initially empty)

As we iterate through the string, we move each character from the right part to the left part by:

1. Adding the character to vis (left part's distinct characters)
2. Decreasing its count in cnt and removing it from cnt if count reaches 0
3. Checking if the number of distinct characters is equal: len(vis) == len(cnt)

The algorithm counts all positions where this equality holds, giving us the total number of good splits.

Intuition

The key insight is that we need to efficiently track the number of distinct characters on both sides of each potential split point. Instead of recalculating the distinct characters for each split from scratch (which would be inefficient), we can use a sliding approach.

Think of it like transferring items from one box to another. Initially, all characters are in the "right" box, and the "left" box is empty. As we move through the string character by character, we transfer each character from the right box to the left box. This way, we only need to update our counts incrementally rather than recalculating everything.

The clever part is how we track distinct characters:

• For the left side, we use a set because we only care about which characters are present, not their frequencies
• For the right side, we use a Counter that tracks frequencies, because when a character's count drops to zero, it's no longer distinct in the right part

As we iterate through position i in the string:

• Everything before position i forms the left part
• Everything from position i onwards forms the right part
• We move character at position i from right to left

This transforms an O(n²) problem (checking every split and counting distinct characters each time) into an O(n) solution. We're essentially maintaining a running state of distinct characters on both sides, updating it in O(1) time as we move our split point through the string.

The condition len(vis) == len(cnt) elegantly checks if both sides have the same number of distinct characters. When this is true, we've found a good split and increment our answer counter.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution implements a sliding window technique with two tracking mechanisms for distinct characters:

1. Initialize the right side counter: Create a Counter object cnt that contains all characters in the string with their frequencies. This represents all distinct characters initially in the right part.

2. Initialize the left side tracker: Create an empty set called vis to track distinct characters in the left part.

3. Iterate through each character: Process each character c in string s one by one:

   a. Add to left side: Add character c to the vis set. This marks it as present in the left part (duplicates are automatically handled by the set).

   b. Remove from right side: Decrease the count of c in cnt by 1. If the count reaches 0, remove the character from cnt entirely using cnt.pop(c). This ensures cnt only contains characters that still exist in the right part.

   c. Check for good split: Compare len(vis) with len(cnt). If they're equal, we have found a good split. Add 1 to ans (using the boolean-to-integer conversion where True becomes 1 and False becomes 0).

4. Return the result: After processing all characters, return ans which contains the total count of good splits.

Time Complexity: O(n) where n is the length of the string. We iterate through the string once, and each operation inside the loop (set addition, counter update, length comparison) takes O(1) time.

Space Complexity: O(k) where k is the number of distinct characters in the string. Both cnt and vis store at most k distinct characters.

The elegance of this approach lies in maintaining a dynamic view of distinct characters on both sides without recalculating from scratch at each position.

Example Walkthrough

Let's walk through the solution with s = "ababa":

Initial Setup:

• cnt = Counter({'a': 3, 'b': 2}) - all characters are in the right part
• vis = set() - left part is empty
• ans = 0

Iteration 1: Process 'a' at index 0

• Add 'a' to vis: vis = {'a'}
• Decrease 'a' in cnt: cnt = {'a': 2, 'b': 2}
• Check: len(vis) = 1, len(cnt) = 2 → Not equal, no increment
• Split would be: "a" | "baba" (1 vs 2 distinct)

Iteration 2: Process 'b' at index 1

• Add 'b' to vis: vis = {'a', 'b'}
• Decrease 'b' in cnt: cnt = {'a': 2, 'b': 1}
• Check: len(vis) = 2, len(cnt) = 2 → Equal! ans = 1
• Split would be: "ab" | "aba" (2 vs 2 distinct) ✓

Iteration 3: Process 'a' at index 2

• Add 'a' to vis: vis = {'a', 'b'} (no change, 'a' already present)
• Decrease 'a' in cnt: cnt = {'a': 1, 'b': 1}
• Check: len(vis) = 2, len(cnt) = 2 → Equal! ans = 2
• Split would be: "aba" | "ba" (2 vs 2 distinct) ✓

Iteration 4: Process 'b' at index 3

• Add 'b' to vis: vis = {'a', 'b'} (no change, 'b' already present)
• Decrease 'b' in cnt: cnt = {'a': 1, 'b': 0} → Remove 'b' → cnt = {'a': 1}
• Check: len(vis) = 2, len(cnt) = 1 → Not equal, no increment
• Split would be: "abab" | "a" (2 vs 1 distinct)

Result: ans = 2 (there are 2 good splits possible)

The key insight: as we move through the string, we're efficiently transferring characters from right to left, updating our distinct character counts in constant time rather than recounting for each split.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the string s exactly once, where n is the length of the string. Within each iteration:

• Adding an element to the set vis takes O(1) time
• Decrementing the counter value takes O(1) time
• Popping from the counter when count reaches 0 takes O(1) time
• Comparing the lengths of vis and cnt takes O(1) time

Since we perform n iterations with O(1) operations in each iteration, the overall time complexity is O(n).

Space Complexity: O(k) where k is the number of unique characters in the string

The space usage comes from:

• cnt: A Counter object that stores at most k unique characters and their frequencies, requiring O(k) space
• vis: A set that stores at most k unique characters, requiring O(k) space

Since k is bounded by the size of the alphabet (at most 26 for lowercase English letters), we can also express this as O(1) for a fixed alphabet size. However, in the general case where k can vary with input, the space complexity is O(k).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Split Boundary

A common mistake is misunderstanding where the split occurs. When iterating through the string, developers might incorrectly think the last character should be included in the split count, but the problem requires both parts to be non-empty. The last iteration would leave the right part empty, making it an invalid split.

Incorrect approach:

for i in range(len(s)):  # Wrong! This would include splitting after the last character
    # Process split...

Correct approach:

for i in range(len(s) - 1):  # Stop before the last character
    # Or when using the character iteration approach:
    for char in s[:-1]:  # Exclude the last character

2. Not Properly Removing Characters from Counter

Forgetting to remove characters with zero count from the counter leads to incorrect distinct character counts. The counter would still contain keys with 0 values, inflating the distinct character count for the right part.

Incorrect approach:

right_counter[char] -= 1
# Forgot to remove when count reaches 0
# len(right_counter) would include characters with 0 count

Correct approach:

right_counter[char] -= 1
if right_counter[char] == 0:
    right_counter.pop(char)  # Must remove to get accurate distinct count

3. Using List Instead of Set for Left Part

Using a list to track distinct characters in the left part would count duplicates, giving an incorrect count of distinct characters.

Incorrect approach:

left_chars = []
left_chars.append(char)  # Would add duplicates
if len(left_chars) == len(right_counter):  # Wrong count!

Correct approach:

left_unique = set()
left_unique.add(char)  # Automatically handles duplicates
if len(left_unique) == len(right_counter):  # Correct distinct count

4. Reinitializing Counter in Each Iteration

Some might try to create a new counter for each potential split position, leading to O(n²) time complexity instead of O(n).

Inefficient approach:

for i in range(len(s) - 1):
    left_part = s[:i+1]
    right_part = s[i+1:]
    left_distinct = len(set(left_part))  # O(n) operation
    right_distinct = len(set(right_part))  # O(n) operation

Efficient approach: Use the sliding window technique with incremental updates as shown in the solution, maintaining O(n) overall complexity.