2024-12-19：分割字符频率相等的最少子字符串

福大大架构师每日一题

发布于 2024-12-19 10:43:49

7400

代码可运行

运行总次数：0

代码可运行

2024-12-19：分割字符频率相等的最少子字符串。用go语言，给定一个字符串 s，你需要将其分割成一个或多个“平衡”子字符串。所谓“平衡”字符串是指其中所有字符出现的次数相同。例如，对于 s = "ababcc"，你可以得到多个合法的分割方式，如 ("abab", "c", "c")、("ab", "abc", "c") 和 ("ababcc")。然而，像 ("a", "bab", "cc")、("aba", "bc", "c") 和 ("ab", "abcc") 这样的分割则是不合法的。请你返回将 s 最少分割成多少个平衡子字符串。

请注意，平衡字符串的定义是：字符串中每个字符的出现次数必须一致。

1 <= s.length <= 1000。

s 只包含小写英文字母。

答案2024-12-19：

chatgpt[1]

题目来自leetcode3144。

大体步骤如下：

1.创建一个字典来存储字符出现的次数。

2.遍历字符串 s，统计每个字符出现的次数。

3.维护一个计数器 count，用来表示当前正在构建的平衡子字符串的数量。

4.遍历 s 中的每个字符，如果当前字符加入后仍能保持平衡，则继续构建同一平衡子字符串，否则增加 count 并重新开始构建下一个平衡子字符串。

5.返回 count 即可得到最少分割的平衡子字符串数量。

时间复杂度：遍历字符串 s 需要 O(n) 的时间复杂度，其中 n 是字符串 s 的长度，因此总体时间复杂度为 O(n)。

空间复杂度：使用一个字典来存储字符出现的次数，额外空间复杂度为 O(1)。

Go完整代码如下：

package main

import(
"fmt"
)

const inf =0x3f3f3f3f

funcminimumSubstringsInPartition(s string)int{
    n :=len(s)
    d :=make([]int, n+1)
for i :=range d {
        d[i]= inf
}
    d[0]=0

for i :=1; i <= n; i++{
        maxCnt :=0
        occCnt :=make(map[byte]int)
for j := i; j >=1; j--{
            occCnt[s[j-1]]++
if occCnt[s[j-1]]> maxCnt {
                maxCnt = occCnt[s[j-1]]
}
if maxCnt*len(occCnt)==(i-j+1)&& d[j-1]!= inf {
if d[i]> d[j-1]+1{
                    d[i]= d[j-1]+1
}
}
}
}
return d[n]
}

funcmain(){
    s :="fabccddg"
    fmt.Println(minimumSubstringsInPartition(s))
}

Rust完整代码如下：

const INF:i32=0x3f3f3f3f;

fnminimum_substrings_in_partition(s:&str)->i32{
letn= s.len();
letmut d=vec![INF; n +1];
    d[0]=0;

foriin1..=n {
letmut max_cnt=0;
letmut occ_cnt: std::collections::HashMap<u8,i32>= std::collections::HashMap::new();

forjin(1..=i).rev(){
letch= s.as_bytes()[j -1];
*occ_cnt.entry(ch).or_insert(0)+=1;

if occ_cnt[&ch]> max_cnt {
                max_cnt = occ_cnt[&ch];
}

if max_cnt * occ_cnt.len()asi32==(i - j +1)asi32&& d[j -1]!= INF {
                d[i]= d[i].min(d[j -1]+1);
}
}
}

    d[n]
}

fnmain(){
lets="fabccddg";
println!("{}",minimum_substrings_in_partition(s));
}