2025-03-05：操作后字符串的最短长度。用go语言，给定一个字符串 s，你需要执行以下操作多次： 1.找一个下标 i，使得

福大大架构师每日一题

发布于 2025-03-06 23:29:37

5900

代码可运行

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

运行总次数：0

代码可运行

2025-03-05：操作后字符串的最短长度。用go语言，给定一个字符串 s，你需要执行以下操作多次：

1.找一个下标 i，使得s[i] 左右两侧至少各有一个与 s[i] 相同的字符。

2.删除掉 s[i] 左边最近的一个与 s[i] 相同的字符。

3.删除掉 s[i] 右边最近的一个与 s[i] 相同的字符。

最后，返回经过所有可能操作后，字符串 s 的最短长度。

1 <= s.length <= 2 * 100000。

s 只包含小写英文字母。

输入：s = "abaacbcbb"。

输出：5。

解释：

我们执行以下操作：

选择下标 2 ，然后删除下标 0 和 3 处的字符，得到 s = "bacbcbb" 。

选择下标 3 ，然后删除下标 0 和 5 处的字符，得到 s = "acbcb" 。

答案2025-03-05：

chatgpt[1]

题目来自leetcode3223。

大体步骤如下：

1.首先，统计字符串 s 中每个字母出现的次数，存储在长度为 26 的数组 cnt 中。

2.初始化一个变量 sum 为 0，用于记录剩余的字母总数。

3.遍历字符串 s：

• 如果字母 s[i] 的计数 cnt[s[i]-'a'] 大于等于 3，则将计数减去 2（保留一个字母，删除两个相邻的字母）。

4.再次遍历数组 cnt，累加每个字母的计数，得到剩余字母的总数 sum。

5.返回 sum 即为字符串 s 经过所有可能操作后的最短长度。

总的时间复杂度为 O(n)，其中 n 为字符串 s 的长度，因为需要遍历字符串 s 两次以及遍历长度为 26 的数组 cnt 一次。

总的额外空间复杂度为 O(1)，因为只使用了常数大小的额外空间，而不随输入规模增加。

Go完整代码如下：

package main

import (
    "fmt"
)

func minimumLength(s string)int {
    size := len(s)
    cnt := make([]int, 26)

    // 计算每个字母出现的次数
    for i := 0; i < size; i++ {
        cnt[s[i]-'a']++
    }

    // 更新字母的计数
    for i := 0; i < size; i++ {
        if cnt[s[i]-'a'] >= 3 {
            cnt[s[i]-'a'] -= 2
        }
    }

    // 计算剩余字母的总数
    sum := 0
    for i := 0; i < 26; i++ {
        sum += cnt[i]
    }

    return sum
}

func main() {
    s := "abaacbcbb"
    result := minimumLength(s)
    fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下：

# -*-coding:utf-8-*-

defminimum_length(s: str) -> int:
    size = len(s)
    cnt = [0] * 26

    # 计算每个字母出现的次数
    for char in s:
        cnt[ord(char) - ord('a')] += 1

    # 更新字母的计数
    for char in s:
        if cnt[ord(char) - ord('a')] >= 3:
            cnt[ord(char) - ord('a')] -= 2

    # 计算剩余字母的总数
    returnsum(cnt)

if __name__ == "__main__":
    s = "abaacbcbb"
    result = minimum_length(s)
    print(result)