3223. 操作后字符串的最短长度

题目描述

给你一个字符串 s 。

你需要对 s 执行以下操作任意次：

选择一个下标 i ，满足 s[i] 左边和右边都至少有一个字符与它相同。
删除 s[i] 左边离它最近且相同的字符。
删除 s[i] 右边离它最近且相同的字符。

请你返回执行完所有操作后， s 的最短长度。

示例 1：

输入：s = "abaacbcbb"

输出：5

解释：
我们执行以下操作：

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

示例 2：

输入：s = "aa"

输出：2

解释：
无法对字符串进行任何操作，所以返回初始字符串的长度。

提示：

1 <= s.length <= 2 * 10⁵
s 只包含小写英文字母。

解法

方法一：计数

我们可以统计字符串中每个字符出现的次数，然后遍历计数数组，如果字符出现的次数为奇数，则最后该字符剩余 $1$ 个，如果字符出现的次数为偶数，则最后该字符剩余 $2$ 个。我们可以将所有字符的剩余个数相加，即为最终字符串的长度。

Python3JavaC++GoTypeScript

class Solution:
    def minimumLength(self, s: str) -> int:
        cnt = Counter(s)
        return sum(1 if x & 1 else 2 for x in cnt.values())

class Solution {
    public int minimumLength(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        int ans = 0;
        for (int x : cnt) {
            if (x > 0) {
                ans += x % 2 == 1 ? 1 : 2;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int minimumLength(string s) {
        int cnt[26]{};
        for (char& c : s) {
            ++cnt[c - 'a'];
        }
        int ans = 0;
        for (int x : cnt) {
            if (x) {
                ans += x % 2 ? 1 : 2;
            }
        }
        return ans;
    }
};

func minimumLength(s string) (ans int) {
    cnt := [26]int{}
    for _, c := range s {
        cnt[c-'a']++
    }
    for _, x := range cnt {
        if x > 0 {
            if x&1 == 1 {
                ans += 1
            } else {
                ans += 2
            }
        }
    }
    return
}

function minimumLength(s: string): number {
    const cnt = new Map<string, number>();
    for (const c of s) {
        cnt.set(c, (cnt.get(c) || 0) + 1);
    }
    let ans = 0;
    for (const x of cnt.values()) {
        ans += x & 1 ? 1 : 2;
    }
    return ans;
}

3223. 操作后字符串的最短长度

题目描述

解法

方法一：计数

评论