Number of Good Ways to Split a String — Solution

Problem

Given a string, count how many ways you can cut it into a non-empty left part and a non-empty right part such that both halves contain the same number of distinct characters.

• Input: s = "aacaba"
• Output: 2
• Explanation: Cutting at index 3 ("aac" | "aba") gives 2 vs 2, and at index 4 ("aaca" | "ba") gives 2 vs 2 — both good.

A counter-example: cutting at index 1 ("a" | "acaba") gives 1 distinct vs 3 distinct — not a good split.

Intuition

The key observation is that as you scan left to right, the distinct character count on the left can only increase (or stay the same), and the count on the right can only decrease. This monotonic structure means you can pre-compute both sides in a single pass each, turning the problem into a simple array comparison.

Approach 1 — Brute Force

For each of the n−1 valid split positions, independently build a character set for the left and right halves and compare their sizes.

1. Iterate split positions from 1 to n−1.
2. Build a set from the left slice s[0..split−1] and another from the right slice s[split..n−1].
3. If the two set sizes are equal, count it as a good split.

1def numSplits(s: str) -> int:
2    count = 0
3    for split in range(1, len(s)):
4        left_distinct = len(set(s[:split]))
5        right_distinct = len(set(s[split:]))
6        if left_distinct == right_distinct:
7            count += 1
8    return count

Time: O(n²) — rebuilding both character sets from scratch at each of the n−1 split points.
Space: O(n) — the character sets are bounded by 26 lowercase letters (O(1)), but the string slices themselves take O(n).

Approach 2 — Prefix and Suffix Arrays

Pre-compute two arrays: how many distinct characters exist from the left up to each index, and from the right down to each index. Then a single linear scan over split positions answers the question in O(1) per query.

1. Build prefix_distinct[i] = number of distinct characters in s[0..i] by scanning left to right, maintaining a running set and recording its size at each position.
2. Build suffix_distinct[i] = number of distinct characters in s[i..n−1] by scanning right to left the same way.
3. For each split position (from 1 to n−1), check if prefix_distinct[split−1] == suffix_distinct[split]; if so, increment the count.

1def numSplits(s: str) -> int:
2    n = len(s)
3    prefix_distinct = [0] * n
4    suffix_distinct = [0] * n
5
6    seen = set()
7    for i in range(n):
8        seen.add(s[i])
9        prefix_distinct[i] = len(seen)
10
11    seen = set()
12    for i in range(n - 1, -1, -1):
13        seen.add(s[i])
14        suffix_distinct[i] = len(seen)
15
16    count = 0
17    for split in range(1, n):   # left = s[0..split-1], right = s[split..n-1]
18        if prefix_distinct[split - 1] == suffix_distinct[split]:
19            count += 1
20    return count

Time: O(n) — three linear passes over the string.
Space: O(n) — two arrays of length n; the running sets hold at most 26 entries (effectively O(1)).

Complexity Summary

Common Mistakes

• Off-by-one on the split index — the left half is s[0..split−1] and the right half is s[split..n−1]; using prefix_distinct[split] instead of prefix_distinct[split−1] includes one extra character on the wrong side.
• Allowing empty halves — valid split positions run from 1 to n−1 (inclusive); splitting at 0 or n leaves one side empty, which the problem forbids.
• Rebuilding the set from scratch per split in the brute force — slicing the string and re-inserting all characters on every iteration is the source of the O(n²) cost; pre-building the arrays is what drops it to O(n).
• Confusing distinct-character count with character frequency — the problem asks how many unique characters appear, not how many times each appears; a set (or counting nonzero entries in a frequency array) is the right structure.
• Forgetting to reset seen between the two passes — reusing the same set for the suffix scan without clearing it will carry over characters from the prefix scan and produce wrong suffix counts.

Related Problems

• subarray-sum-equals-k — same prefix-array technique to answer split-point queries in O(1) after an O(n) precomputation
• contiguous-array — uses prefix counts to detect a balanced split property across an index
• find-all-anagrams-in-a-string — comparing character-set properties between two substrings using sliding windows
• permutation-in-string — tracking the distinct character profile of a window and comparing it to a target
• longest-substring-without-repeating-characters — expanding and shrinking a window while maintaining a live distinct-character count