AlgoMaster Logo

Number of Good Ways to Split a String

mediumFrequency6 min readUpdated June 23, 2026

Understanding the Problem

We need to find every index i (from 1 to n-1) where we cut the string into s[0..i-1] and s[i..n-1], and both halves have the same number of distinct characters.

The brute force idea is to try every split point and count distinct characters on each side. Counting from scratch at every position repeats work. As the split point slides one position to the right, only one character moves from the right half to the left half. The distinct counts change incrementally, so we can update them in O(1) per step instead of recounting.

Key Constraints:

  • 1 <= s.length <= 10^5 → We need O(n) or O(n log n). An O(n^2) brute force that rebuilds sets at every split will be too slow.
  • s consists of only lowercase English letters → At most 26 distinct characters. This means any frequency map or set we maintain has bounded size, so operations on it are O(1).

Approach 1: Brute Force

Intuition

For every possible split position, build a set of characters for the left half and a set for the right half, then check if their sizes match. There are n-1 split positions, and at each one we scan both substrings.

Algorithm

  1. For each split index i from 1 to n-1:
    • Count distinct characters in s[0..i-1] using a set.
    • Count distinct characters in s[i..n-1] using a set.
    • If both counts are equal, increment the result.
  2. Return the result.

Example Walkthrough

1Try all split positions from 1 to n-1
0
a
1
a
2
c
3
a
4
b
5
a
1/7

Code

Rebuilding both sets at every split point is the source of the quadratic cost. The next approach precomputes the distinct count from each end once, so every split check becomes O(1).

Approach 2: Prefix and Suffix Distinct Counts

Intuition

Instead of recomputing distinct counts at every split, we precompute them. Scan left-to-right and record how many distinct characters appear up to each index. Do the same from right-to-left. For each split point, compare the two precomputed values.

This follows the prefix sum pattern, except we track running set sizes instead of running totals.

Algorithm

  1. Create an array prefixDistinct of size n, where prefixDistinct[i] is the number of distinct characters in s[0..i].
  2. Create an array suffixDistinct of size n, where suffixDistinct[i] is the number of distinct characters in s[i..n-1].
  3. For each split point i from 1 to n-1, check if prefixDistinct[i-1] == suffixDistinct[i].
  4. Count and return the matches.

Example Walkthrough

s
1Start with s = "aacaba"
0
a
1
a
2
c
3
a
4
b
5
a
prefixDistinct
1Initialize prefixDistinct array
0
0
1
0
2
0
3
0
4
0
5
0
suffixDistinct
1Initialize suffixDistinct array
0
0
1
0
2
0
3
0
4
0
5
0
1/7

Code

This approach runs in O(n) time but allocates two arrays of size n. The next approach keeps the same time bound while replacing both arrays with a fixed set of counters, dropping the space to O(1).

Approach 3: Single Pass with Frequency Map

Intuition

Start by putting all character frequencies into a "right" frequency map. Then sweep the split point from left to right. At each step, move the current character from the right side to the left side. When a character is added to the left for the first time, the left distinct count goes up by one. When a character's frequency in the right map drops to zero, the right distinct count goes down by one. Tracking these two counts is enough to test every split.

This replaces both arrays with a single set of counters and solves the problem in one sweep after the initial frequency count.

Algorithm

  1. Build a frequency map of all characters in s (this represents the "right" side initially).
  2. Track rightDistinct as the number of keys in this map and leftDistinct as 0.
  3. Sweep i from 0 to n-2 (these are the split points):
    • Add s[i] to the left side: if it's the first occurrence on the left, increment leftDistinct.
    • Remove s[i] from the right side: decrement its frequency. If frequency reaches 0, decrement rightDistinct.
    • If leftDistinct == rightDistinct, this is a good split.
  4. Return the count.

Example Walkthrough

s
1Init: rightDistinct=3, leftDistinct=0
0
a
1
a
2
c
3
a
4
b
5
a
right (3 distinct)
rightFreq
1Count all chars: rightFreq = {a:4, c:1, b:1}
a
:
4
c
:
1
b
:
1
1/7

Code