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

福大大架构师每日一题

发布于 2024-10-21 11:01:52

900

发布于 2024-10-21 11:01:52

文章被收录于专栏：福大大架构师每日一题

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;

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