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 <= 10^5s consists of only lowercase English letters.
The description was taken from https://leetcode.com/problems/number-of-good-ways-to-split-a-string/.
#O(N) Time, O(1) Space
class Solution:
def numSplits(self, s: str) -> int:
left, right = {}, {}
output = 0
for char in s:
if char in right:
right[char] += 1
else:
right[char] = 1
for char in s:
right[char] -= 1
if right[char] == 0:
del right[char]
left[char] = True
if len(left) == len(right):
output += 1
return outputIf we look at the example, we can see that the substrings are put into two buckets and if those buckets have an even number of unique values then it is considered a good split.
We can roll with that same intuition through the implementation of two HashMaps to track the frequencies of the characters. If we ever find that the length of the HashMaps are the same, meaning there is the same number of keys between both, then we will increment our count by one.
Let's start by initializing our left and right buckets.
left, right = {}, {}
We'll also need an output count.
output = 0
We'll first add each value to the bucket, or increment its frequency if we already placed it there within a previous iteration.
for char in s:
if char in right:
right[char] += 1
else:
right[char] = 1
Now we will go through the string once more and remove each character from the right bucket so that we can place it into the left one.
for char in s:
right[char] -= 1
If we find that after decrementing this value from the right bucket, however, we'll need to make sure that we remove the key so that it doesn't contribute to the length of the bucket.
if right[char] == 0:
del right[char]
Now that we have removed the number from the right bucket, we'll add the value to the left bucket.
We don't actually need to increment any frequency values here because we won't be removing them from the left bucket and all we care about is the length.
left[char] = True
If the length of the buckets are the same, meaning there is an even number of keys, meaning there is an even number of unique values, then we will increment our output by one.
if len(left) == len(right):
output += 1
Once we have counted even buckets, we'll return the output.
return output