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

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)

在这里插入图片描述引用链接