You are given a string s, a split is called good if you can split s into 2 non-empty strings p and q where its concatenation is equal to s and the number of distinct letters in p and q are 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").


Example 3:

Input: s = "aaaaa"
Output: 4
Explanation: All possible splits are good.

Example 4:

Input: s = "acbadbaada"
Output: 2


Constraints:

• s contains only lowercase English letters.
• 1 <= s.length <= 10^5

## Solution: Sliding Window

1. Count the frequency of each letter and count number of unique letters for the entire string as right part.
2. Iterate over the string, add current letter to the left part, and remove it from the right part.
3. We only
1. increase the number of unique letters when its frequency becomes to 1
2. decrease the number of unique letters when its frequency becomes to 0

Time complexity: O(n)
Space complexity: O(1)

## Python3

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode