Number of Good Ways to Split a String - Solution & Explanation
Problem Statement
You are given a string s.
A split is called good if you can split s into two non-empty strings sleft and sright where their concatenation is equal to s (i.e., sleft + sright = s) and the number of distinct letters in sleft and sright is the same.
Return the number of good splits you can make in s.
Example 1:
Input: s = "aacaba"
Output: 2
Explanation: There are 5 ways to split "aacaba" and 2 of them are good.
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.
Example 2:
Input: s = "abcd"
Output: 1
Explanation: Split the string as follows ("ab", "cd").
Constraints:
1 <= s.length <= 105sconsists of only lowercase English letters.
Approach Overview
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.
Approach 1: Approach 1: Prefix and Suffix Distinct Count Arrays
In this approach, we utilize two arrays: left_distinct to count distinct characters from the start to each character, and right_distinct from each character to the end of the string. Using these arrays, we can easily compare the number of distinct characters on both sides of any potential split position.
First, we traverse the string from left to right to fill left_distinct, counting distinct characters as we go. Similarly, we populate right_distinct by traversing from right to left. Finally, we iterate through both arrays and compare values at each position to tally the number of good splits.
The implementation starts by initializing arrays to track distinct character counts from the left and right. By iterating over the input string, we populate these arrays, counting distinct characters for each position. Finally, a loop compares these counts at each split point to determine the number of good splits.
Complexity
Time Complexity: O(n), where n is the length of the string, since we traverse it a small constant number of times.
Space Complexity: O(1), considering the character set size is constant (26 for lowercase letters).
Approach 2: Approach 2: Two-Pass with Single Array
This method reduces space consumption by employing a single array and two counters: one for distinct prefixes and another for suffixes. During the first pass, distinct prefix counts are recorded. The second backward pass updates this single array with suffix counts; simultaneously, good splits are counted when prefix and suffix counts align.
Here, the method capitalizes on a single array to store diverse prefix values. During reverse iteration, suffix distinct character totals are handled by a tracker, identifying good splits as these counts equate.
Complexity
Time Complexity: O(n) as it involves traversals in both directions.
Space Complexity: O(1) considering the fixed character set size for counting arrays.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Prefix and Suffix Distinct Count Arrays | Time Complexity: O(n), where n is the length of the string, since we traverse it a small constant number of times. |
| Approach 2: Two-Pass with Single Array | Time Complexity: O(n) as it involves traversals in both directions. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix and Suffix Distinct Count Arrays | O(n) | O(n) | Best general solution. Easy to reason about and commonly used in interviews. |
| Two-Pass with Single Array | O(n) | O(n) | When you want slightly cleaner logic by computing suffix counts first and updating prefix counts on the fly. |
Video Solution
number of good ways to split a string leetcode | leetcode 1525 • Naresh Gupta • 6,312 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Good Ways to Split a String easy or hard?
Number of Good Ways to Split a String Python/Java solution
How to solve Number of Good Ways to Split a String in O(n)?
What is the best approach for Number of Good Ways to Split a String?
Is Number of Good Ways to Split a String asked at Google/Amazon/Meta?
What data structure is used in Number of Good Ways to Split a String?
What is the time complexity of Number of Good Ways to Split a String?
Ready to solve this problem?
Practice Number of Good Ways to Split a String with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor