Number of Good Ways to Split a String
Problem Description
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 <= 105
sconsists of only lowercase English letters.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The brute force approach involves using a nested loop to try every possible split point and count unique characters on both sides of the split. While this method is straightforward, it is inefficient because it involves recalculating the unique character count for both substrings at every possible split point.
Steps:
- Initialize a counter to keep track of good splits.
- Loop over possible split points from 1 to n-1 (where n is the length of the string).
- For each split point, split the string into two parts and count the unique characters in each part.
- If the number of unique characters in both parts is equal, increment the good split counter.
Code:
- Time Complexity: O(n^2) - For each split point, counting unique characters can take up to O(n) time.
- Space Complexity: O(1) - The space used by the boolean array is constant in size.
2. Optimized Approach using Frequency Maps
Intuition:
To improve efficiency, we can use two frequency maps to track character counts on both sides of the split. We start with all characters in the 'right' map, and as we process each character, we move it from the 'right' map to the 'left' map until the split point is found. This allows maintaining constant time complexity for adjusting character counts and only recalculates the number of unique characters at each split.
Steps:
- Initialize two integer arrays
leftFreqandrightFreqto keep track of character occurrences on both sides. - Traverse the string once to populate the
rightFreqarray. - As we iterate over possible split points, adjust the counts in
leftFreqandrightFreqas characters move from right to left. - Use two counters
leftUniqueandrightUniqueto track the number of unique characters in each partition as they evolve. - Whenever these two counters are equal, it is a good split.
Code:
- Time Complexity: O(n) - We traverse the string a constant number of times.
- Space Complexity: O(1) - Frequency arrays use constant extra space.