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 mainimport("fmt")func maximumLengthSubstring(s string)(ans int){ cnt :=[26]int{} left :=0for 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;fnmax(a:usize, b:usize)->usize{if a > b { a}else{ b}}fnmaximum_length_substring(s:&str)->usize{letmut cnt:HashMap<char,usize>=HashMap::new();letmut left=0;letmut 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}fnmain(){lets="bcbbbcba";println!("{}",maximum_length_substring(s));}

在这里插入图片描述