README.md

comments	difficulty	edit_url	rating	source	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3223.Minimum%20Length%20of%20String%20After%20Operations/README.md	1445	第 135 场双周赛 Q2	哈希表 字符串 计数

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

English Version

题目描述

给你一个字符串 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 * 105
• s 只包含小写英文字母。

解法

方法一：计数

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

时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(|\Sigma|)$，其中 $|\Sigma|$ 为字符集的大小，本题中 $|\Sigma| = 26$。

Python3

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

Java

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

C++

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

Go

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
}

TypeScript

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