DSA problem
Number of Good Ways to Split a String
You are given a string s.
A split is called good if you can split s into two non-empty strings s_left and s_right where their concatenation is equal to s (i.e., s_left + s_right = s) and the number of distinct letters in s_left and s_right is the same.
Return the number of good splits you can make in s.
For instance, splitting "aacaba" after the third character gives "aac" and "aba"; the left side has 2 distinct letters and the right side has 2 distinct letters, so that split is good.
Examples
Example 1
Input:
s = "aacaba"Output:
2Explanation: There are 5 ways to split "aacaba" and 2 of them are good. ("aac", "aba") -> left has {a,c}=2 distinct, right has {a,b}=2 distinct. ("aaca", "ba") -> left has {a,c}=2 distinct, right has {b,a}=2 distinct.
Example 2
Input:
s = "abcd"Output:
1Explanation: The only good split is splitting in the middle: ("ab", "cd"), each side has 2 distinct letters.
Example 3
Input:
s = "aaaaa"Output:
4Explanation: Every one of the 4 possible splits is good because both sides always contain exactly 1 distinct letter.
Constraints
- 1 <= s.length <= 10^5
- s consists of only lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.