代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个字符串 s
,一个分割被称为 「好分割」 当它满足:将 s
分割成 2 个字符串 p
和 q
,它们连接起来等于 s
且 p
和 q
中不同字符的数目相同。
请你返回 s
中好分割的数目。
示例 1:
"aacaba"
示例 2:
输入:s = "abcd" 输出:1 解释:好分割为将字符串分割成 ("ab", "cd") 。
示例 3:
输入:s = "aaaaa" 输出:4 解释:所有分割都是好分割。
示例 4:
输入:s = "acbadbaada" 输出:2
提示:
s
只包含小写英文字母。1 <= s.length <= 10^5
我们维护两个哈希表,分别记录左侧出现的字符、右侧的字符以及出现的次数。初始时,左侧的哈希表为空,右侧的哈希表为字符串 $s$ 中所有字符出现的次数。
接下来,我们从左到右遍历字符串 $s$,对于遍历到的字符 $c$,我们将其加入左侧的哈希表,同时将其在右侧的哈希表中的出现次数减一。如果减一后,右侧哈希表中的出现次数为 0,则将其从右侧哈希表中移除。然后,我们判断左侧哈希表中的键值对数量是否与右侧哈希表中的键值对数量相等,如果相等,则将答案加一。
最终,我们返回答案即可。
时间复杂度为 $O(n)$,空间复杂度为 $O(n)$。其中 $n$ 为字符串 $s$ 的长度。
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
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;
}
}
class Solution {
public:
int numSplits(string s) {
unordered_map<char, int> cnt;
for (char& c : s) {
++cnt[c];
}
unordered_set<char> vis;
int ans = 0;
for (char& c : s) {
vis.insert(c);
if (--cnt[c] == 0) {
cnt.erase(c);
}
ans += vis.size() == cnt.size();
}
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
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。