2024-10-16：用go语言，找出一个字符串中每个字符最多出现两次的最长子串，并返回该子串的最大长度。

输入： s = “bcbbbcba”。

输出： 4。

解释：

以下子字符串长度为 4，并且每个字符最多出现两次："bcbbbcba"的右4个字符。

答案2024-10-16：

chatgpt

题目来自leetcode3090。

大体步骤如下：

1.字符串处理：遍历给定的字符串 “bcbbbcba”，对每个字符计数，确保每个字符最多出现两次。

2.滑动窗口法：使用滑动窗口法来找出符合条件的最长子串。维护一个窗口，当窗口中的字符重复超过两次，则左边界向右移动，直到满足每个字符最多出现两次的条件。

3.更新最大长度：在窗口移动过程中，不断更新最大子串的长度。

4.返回结果：最终返回找到的最大子串的长度。

• 总时间复杂度：整体通过一次遍历来完成，因此总时间复杂度为 O(n)，其中 n 为字符串的长度。

• 额外空间复杂度：额外使用了长度为 26 的数组用于存储字符出现次数，因此额外空间复杂度为 O(1)。

Go完整代码如下：

package main

import (
	"fmt"
)

func maximumLengthSubstring(s string) (ans int) {
	cnt := [26]int{}
	left := 0
	for i, b := range s {
		b -= 'a'
		cnt[b]++
		for cnt[b] > 2 {
			cnt[s[left]-'a']--
			left++
		}
		ans = max(ans, i-left+1)
	}
	return
}

func main() {
	s := "bcbbbcba"
	fmt.Println(maximumLengthSubstring(s))
}

Rust完整代码如下：

use std::collections::HashMap;

fn max(a: usize, b: usize) -> usize {
    if a > b {
        a
    } else {
        b
    }
}

fn maximum_length_substring(s: &str) -> usize {
    let mut cnt: HashMap<char, usize> = HashMap::new();
    let mut left = 0;
    let mut ans = 0;

    for (i, c) in s.chars().enumerate() {
        *cnt.entry(c).or_insert(0) += 1;

        while cnt[&c] > 2 {
            *cnt.entry(s.chars().nth(left).unwrap()).or_insert(0) -= 1;
            left += 1;
        }

        ans = max(ans, i - left + 1);
    }

    ans
}

fn main() {
    let s = "bcbbbcba";
    println!("{}", maximum_length_substring(s));
}