Number of Good Ways to Split a String

Number of Good Ways to Split a String

What is this problem about?

The Number of Good Ways to Split a String problem asks: for how many split positions can you divide a string into two non-empty parts such that both parts have the same number of distinct characters? This coding problem uses prefix and suffix distinct-character counts, efficiently maintained with a hash map or bit manipulation.

Why is this asked in interviews?

Meta, Amazon, and Google ask this because it tests efficient prefix/suffix tracking of distinct character counts. A brute-force O(n²) approach is too slow; the O(n) solution uses prefix sets and suffix sets updated incrementally. The hash table, string, bit manipulation, and dynamic programming interview pattern is applied.

Algorithmic pattern used

Two-pass distinct count tracking. Pass 1 (left to right): compute leftDistinct[i] = number of distinct characters in s[0..i]. Pass 2 (right to left): compute rightDistinct[i] = number of distinct characters in s[i..n-1]. For each split point (between index i and i+1): count if leftDistinct[i] == rightDistinct[i+1].

Use bit manipulation: represent character sets as 26-bit integers. Adding a character = OR with bit for that character. Count = popcount.

Example explanation

s = "aacaba". Left distinct: a=1,a=1,c=2,a=2,b=3,a=3. Right distinct (from right): a=1,b=2,a=2,a=2,c=2,a=1... Recompute properly. Split at position 2 (left="aac", right="aba"): left distinct=2, right distinct=2 ✓. Count all valid splits.

Common mistakes candidates make

• O(n²) recomputing distinct counts from scratch for each split.
• Not handling the boundary: splits must produce two non-empty parts (positions 0 to n-2).
• Counting characters instead of distinct character count.
• Confusing "same number of distinct characters" with "same set of distinct characters."

Interview preparation tip

Two-pass prefix/suffix array problems are extremely common. For any property P, precompute leftP[i] and rightP[i], then compare them at each split point. For distinct character count, a 26-bit integer bitmask is elegant: OR to add a character, popcount to get distinct count. Practice building prefix/suffix arrays for various properties (distinct chars, sum, max, min) — this is a reusable template for many string and array split problems.