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 mainimport ( "fmt")const inf = 0x3f3f3f3ffunc minimumSubstringsInPartition(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]}func main() { s := "fabccddg" fmt.Println(minimumSubstringsInPartition(s))}

Rust完整代码如下：const INF: i32 = 0x3f3f3f3f;fn minimum_substrings_in_partition(s: &str) -> i32 { let n = s.len(); let mut d = vec![INF; n + 1]; d[0] = 0; for i in 1..=n { let mut max_cnt = 0; let mut occ_cnt: std::collections::HashMap<u8, i32> = std::collections::HashMap::new(); for j in (1..=i).rev() { let ch = 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() as i32 == (i - j + 1) as i32 && d[j - 1] != INF { d[i] = d[i].min(d[j - 1] + 1); } } } d[n]}fn main() { let s = "fabccddg"; println!("{}", minimum_substrings_in_partition(s));}

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP