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 obvious: try every split point and count distinct characters on each side. But counting distinct characters from scratch at every position is wasteful. The key observation is that as we slide the split point one position to the right, only one character moves from the right half to the left half. So the distinct counts change incrementally, and we can track them efficiently.

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

The most direct approach: 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 the left and right substrings.

Algorithm

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.

Return the result.

Example Walkthrough

1Try all split positions from 1 to n-1

1/7

Code

Complexity Analysis

Time Complexity: O(n^2). We try n-1 split points. At each split, we scan up to n characters to build two sets. That gives us O(n) work per split and O(n^2) overall.
Space Complexity: O(n). Each set can hold up to n characters in the worst case (all unique). Though bounded by 26, the substrings themselves can be up to length n.

At every split point, we rebuild the left and right sets from scratch. But moving the split one position to the right only changes one character. What if we precomputed the distinct counts from both ends so each check is O(1)?

Approach 2: Prefix and Suffix Distinct Counts

Intuition

Instead of recomputing distinct counts at every split, we can precompute them. Scan left-to-right and record how many distinct characters we've seen up to each index. Do the same from right-to-left. Then for each split point, just compare the two precomputed values.

This is essentially the prefix sum idea, but instead of summing values, we're tracking set sizes.

Algorithm

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

Why does this work?

The prefix array captures a monotonically non-decreasing sequence: as we include more characters from the left, we can only see the same or more distinct characters. The suffix array works the same way from the right. At any split point i, prefixDistinct[i-1] tells us the distinct count of the left half and suffixDistinct[i] tells us the distinct count of the right half, both computed in O(1) after the preprocessing.

Example Walkthrough

1Start with s = "aacaba"

prefixDistinct

1Initialize prefixDistinct array

suffixDistinct

1Initialize suffixDistinct array

1/7

Code

Complexity Analysis

Time Complexity: O(n). Three separate passes through the string, each taking O(n). Set operations are O(1) since there are at most 26 characters.
Space Complexity: O(n). Two arrays of size n for the prefix and suffix distinct counts.

This approach achieves O(n) time but uses two auxiliary arrays of size n. Can we track the same information using just two counters and a single sweep, eliminating both arrays?

Approach 3: Single Pass with Frequency Map

Intuition

Here's the idea: 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. When a character's frequency in the right map drops to zero, the right distinct count goes down. We just need to track these two counts.

This eliminates both arrays and solves the problem in a single pass (after the initial frequency count).

Algorithm

Build a frequency map of all characters in s (this represents the "right" side initially).
Track rightDistinct as the number of keys in this map and leftDistinct as 0.
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.

Return the count.

Example Walkthrough

1Init: rightDistinct=3, leftDistinct=0

right (3 distinct)

rightFreq

1Count all chars: rightFreq = {a:4, c:1, b:1}

1/7

Code

Complexity Analysis

Time Complexity: O(n). One pass to build the initial frequency map, one pass to sweep the split point. Each step does O(1) work.
Space Complexity: O(1). We use arrays of size 26 for the frequency map and the "seen" tracker. This is constant regardless of input size.

Number of Good Ways to Split a String

Understanding the Problem

Key Constraints:

Approach 1: Brute Force

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Prefix and Suffix Distinct Counts

Intuition

Algorithm

Example Walkthrough

Code

Approach 3: Single Pass with Frequency Map

Intuition

Algorithm

Example Walkthrough

Code

Get Premium