Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1525.html
1525. Number of Good Ways to Split a String (Medium)
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
Related Topics:
String, Bit Manipulation
Solution 1.
Simply use a linear scan and increment the answer if the left unique count equals the right unique count. If the left unique count is greater than the left one, break the loop.
// OJ: https://leetcode.com/problems/number-of-good-ways-to-split-a-string/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int numSplits(string s) {
int total[26] = {}, left[26] = {}, ans = 0;
for (char c : s) total[c - 'a']++;
for (char c : s) {
++left[c - 'a'];
int L = 0, R = 0;
for (int i = 0; i < 26; ++i) {
if (left[i]) ++L;
if (total[i] - left[i]) ++R;
}
if (L == R) ++ans;
if (L > R) break;
}
return ans;
}
};
Another implementation that doesn’t require the O(26)
check
// OJ: https://leetcode.com/problems/number-of-good-ways-to-split-a-string/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int numSplits(string s) {
int right[26] = {}, left[26] = {}, ans = 0, L = 0, R = 0;
for (char c : s ) R += right[c - 'a']++ == 0;
for (char c : s) {
L += left[c - 'a']++ == 0;
R -= right[c - 'a']-- == 1;
ans += L == R;
if (L > R) break;
}
return ans;
}
};
-
class Solution { public int numSplits(String s) { Map<Character, Integer> map1 = new HashMap<Character, Integer>(); Map<Character, Integer> map2 = new HashMap<Character, Integer>(); int length = s.length(); for (int i = 0; i < length; i++) { char c = s.charAt(i); int count = map2.getOrDefault(c, 0) + 1; map2.put(c, count); } int goodSplits = 0; for (int i = 0; i < length - 1; i++) { char c = s.charAt(i); int count1 = map1.getOrDefault(c, 0) + 1; map1.put(c, count1); int count2 = map2.get(c) - 1; if (count2 > 0) map2.put(c, count2); else map2.remove(c); if (map1.size() == map2.size()) goodSplits++; else if (map1.size() > map2.size()) break; } return goodSplits; } } ############ class Solution { public int numSplits(String s) { Map<Character, Integer> cnt = new HashMap<>(); for (char c : s.toCharArray()) { cnt.merge(c, 1, Integer::sum); } Set<Character> vis = new HashSet<>(); int ans = 0; for (char c : s.toCharArray()) { vis.add(c); if (cnt.merge(c, -1, Integer::sum) == 0) { cnt.remove(c); } if (vis.size() == cnt.size()) { ++ans; } } return ans; } }
-
// OJ: https://leetcode.com/problems/number-of-good-ways-to-split-a-string/ // Time: O(N) // Space: O(1) class Solution { public: int numSplits(string s) { int total[26] = {}, left[26] = {}, ans = 0; for (char c : s) total[c - 'a']++; for (char c : s) { ++left[c - 'a']; int L = 0, R = 0; for (int i = 0; i < 26; ++i) { if (left[i]) ++L; if (total[i] - left[i]) ++R; } if (L == R) ++ans; if (L > R) break; } return ans; } };
-
class Solution: def numSplits(self, s: str) -> int: cnt = Counter(s) vis = set() ans = 0 for c in s: vis.add(c) cnt[c] -= 1 if cnt[c] == 0: cnt.pop(c) ans += len(vis) == len(cnt) return ans
-
func numSplits(s string) (ans int) { cnt := map[rune]int{} for _, c := range s { cnt[c]++ } vis := map[rune]bool{} for _, c := range s { vis[c] = true cnt[c]-- if cnt[c] == 0 { delete(cnt, c) } if len(vis) == len(cnt) { ans++ } } return }