Number of Good Ways to Split a String - Video Solutions

Problem Overview: You are given a string s. Split it into two non-empty parts and count how many split positions produce the same number of distinct characters on the left and right sides.

The challenge is computing distinct character counts efficiently for every split. A naive approach recomputes sets repeatedly, which becomes expensive. Efficient solutions track distinct counts incrementally using arrays or hash-based tracking.

Approach 1: Prefix and Suffix Distinct Count Arrays (O(n) time, O(n) space)

This approach precomputes the number of unique characters seen from both directions. First iterate left to right and store the distinct count at each index in a prefix array. Use a hash set or frequency array to track characters you've already encountered. Then iterate from right to left and build a suffix array that stores distinct counts for the substring starting at each index.

Once both arrays are built, check every split position i. If prefix[i] equals suffix[i+1], that split is valid. Increment the answer. Each character is processed a constant number of times, giving O(n) time. The tradeoff is the additional O(n) memory for the two arrays.

This technique appears frequently in string problems where information about prefixes and suffixes must be reused across many positions.

Approach 2: Two-Pass with Single Array (O(n) time, O(n) space)

You can reduce memory usage by storing only one side explicitly. First compute the suffix distinct counts and store them in an array. Then iterate from the left while maintaining a set (or frequency array) of characters already seen. Each step updates the left-side distinct count dynamically.

At index i, compare the current left distinct count with the precomputed suffix[i+1]. If they match, the split is good. This avoids building a separate prefix array and keeps the algorithm simple.

The logic relies on constant-time character tracking using either a frequency array of size 26 (for lowercase letters) or a hash table. Overall complexity remains O(n) time with O(n) space due to the suffix array.

This pattern resembles prefix-style preprocessing often seen in dynamic programming and counting problems where you reuse earlier results instead of recomputing them.

Recommended for interviews: Interviewers typically expect the prefix/suffix distinct counting idea. It demonstrates that you can transform repeated substring computations into a linear scan. Starting with the brute-force idea (rebuilding sets for every split) shows understanding of the problem, but the optimal O(n) solution shows algorithmic maturity and familiarity with prefix-based preprocessing.