Problem description:

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:

1
2
3
4
5
6
7
8
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:

1
2
3
Input: s = "abcd"
Output: 1
Explanation:Split the string as follows ("ab", "cd").

Example 3:

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

Example 4:

1
2
Input: s = "acbadbaada"
Output: 2

Constraints:

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

Solution:

Counters to count the number of distinct characters in left and right side

leftCounter start with 0

rightCounter start with full string, subtract the frequency during traverse

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def numSplits(self, s: str) -> int:
        leftCounter = Counter()
        rightCounter = Counter(s)
        res = 0
        for c in s:
            leftCounter[c] += 1
            rightCounter[c] -= 1
            if rightCounter[c] == 0:
                del rightCounter[c]
            if len(leftCounter) == len(rightCounter):
                res += 1
        return res

time complexity: $O()$
space complexity: $O()$
reference:
related problem: