class Solution {
public:
int numSplits(string s) {
}
};
1525. 字符串的好分割数目
给你一个字符串 s ，一个分割被称为 「好分割」 当它满足：将 s 分割成 2 个字符串 p 和 q ，它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。
请你返回 s 中好分割的数目。
示例 1：
输入：s = "aacaba"
输出：2
解释：总共有 5 种分割字符串 "aacaba" 的方法，其中 2 种是好分割。
("a", "acaba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aa", "caba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aac", "aba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aaca", "ba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aacab", "a") 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。
示例 2：
输入：s = "abcd"
输出：1
解释：好分割为将字符串分割成 ("ab", "cd") 。
示例 3：
输入：s = "aaaaa" 输出：4 解释：所有分割都是好分割。
示例 4：
输入：s = "acbadbaada" 输出：2
提示：
s 只包含小写英文字母。1 <= s.length <= 10^5原站题解
golang 解法, 执行用时: 28 ms, 内存消耗: 6.1 MB, 提交时间: 2022-11-27 11:11:19
func numSplits(s string) int {
n:=len(s)
m:=map[byte]int{}
dp:=make([]int,n)
for i:=0;i<n;i++{
m[s[i]]++
dp[i]=len(m)
}
ans:=0
for i:=0;i<n;i++{
m[s[i]]--
if m[s[i]]==0{
delete(m, s[i])
}
l,r:=dp[i],len(m)
if l==r{
ans++
}
}
return ans
}
cpp 解法, 执行用时: 28 ms, 内存消耗: 7.8 MB, 提交时间: 2022-11-27 11:11:01
class Solution {
public:
int numSplits(string& s) {
int ret = 0;
unordered_map<char, int> um, um2; //统计字符
for(char& c : s){
um2[c]++;
}
for(char& c : s){
um[c]++;
um2[c]--;
if(um2[c] == 0) um2.erase(c);
if(um.size() == um2.size()) ret++;
}
return ret;
}
};
java 解法, 执行用时: 4 ms, 内存消耗: 42 MB, 提交时间: 2022-11-27 11:10:32
class Solution {
public int numSplits(String s) {
int n = s.length();
int[] left = new int[n + 2];
int[] right = new int[n + 2];
boolean[] recLeft = new boolean[26];
boolean[] recRight = new boolean[26];
for (int i = 1; i <= n; i++) {
int c = s.charAt(i - 1) - 'a';
if (recLeft[c]) {
left[i] = left[i - 1];
} else {
recLeft[c] = true;;
left[i] = left[i - 1] + 1;
}
}
for (int i = n; i > 0; i--) {
int c = s.charAt(i - 1) - 'a';
if (recRight[c]) {
right[i] = right[i + 1];
} else {
recRight[c] = true;
right[i] = right[i + 1] + 1;
}
}
int ret = 0;
for (int i = 1; i < n; i++) {
if (left[i] == right[i + 1]) {
ret++;
}
}
return ret;
}
}
python3 解法, 执行用时: 176 ms, 内存消耗: 16.8 MB, 提交时间: 2022-11-27 11:10:14
class Solution:
def numSplits(self, s: str) -> int:
n = len(s)
left, right = [0] * (n + 2), [0] * (n + 2)
rec_left = [False] * 26
rec_right = [False] * 26
for i in range(1, n + 1):
c = ord(s[i - 1]) - ord("a")
if rec_left[c]:
left[i] = left[i - 1]
else:
rec_left[c] = True
left[i] = left[i - 1] + 1
for i in range(n, 0, -1):
c = ord(s[i - 1]) - ord("a")
if (rec_right[c]):
right[i] = right[i + 1]
else:
rec_right[c] = True
right[i] = right[i + 1] + 1
ret = sum(1 for i in range(1, n) if left[i] == right[i + 1])
return ret