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

题目来自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

func 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));
}