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:
scontains only lowercase English letters.1 <= s.length <= 10^5
Solution: Sliding Window
- Count the frequency of each letter and count number of unique letters for the entire string as right part.
- Iterate over the string, add current letter to the left part, and remove it from the right part.
- We only
- increase the number of unique letters when its frequency becomes to 1
- decrease the number of unique letters when its frequency becomes to 0
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public: int numSplits(string s) { vector<int> r(26); vector<int> l(26); int cr = 0; for (char c : s) cr += (++r[c - 'a'] == 1); int ans = 0; int cl = 0; for (char c : s) { cl += (++l[c - 'a'] == 1); cr -= (--r[c - 'a'] == 0); ans += cl == cr; } return ans; } }; |
java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public int numSplits(String s) { int[] l = new int[26]; int[] r = new int[26]; int ans = 0; int cl = 0; int cr = 0; for (char c : s.toCharArray()) if (++r[c - 'a'] == 1) ++cr; for (char c : s.toCharArray()) { if (++l[c - 'a'] == 1) ++cl; if (--r[c - 'a'] == 0) --cr; if (cl == cr) ++ans; } return ans; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution: def numSplits(self, s: str) -> int: s = [ord(c) - ord('a') for c in s] l, r = [0] * 26, [0] * 26 cl, cr, ans = 0, 0, 0 for c in s: r[c] += 1 if r[c] == 1: cr += 1 for c in s: l[c] += 1 r[c] -= 1 if l[c] == 1: cl += 1 if r[c] == 0: cr -= 1 if cl == cr: ans += 1 return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment