Skip to content

Latest commit

 

History

History
204 lines (163 loc) · 5.55 KB

README.md

File metadata and controls

204 lines (163 loc) · 5.55 KB
Raw
comments difficulty edit_url rating source tags
true
中等
1423
第 124 场双周赛 Q2
数组
哈希表
计数
排序

3039. 进行操作使字符串为空

English Version

题目描述

给你一个字符串 s 。

请你进行以下操作直到 s 为 空 ：

  • 每次操作 依次 遍历 'a' 到 'z'，如果当前字符出现在 s 中，那么删除出现位置 最早 的该字符（如果存在的话）。

例如，最初 s = "aabcbbca"。我们执行下述操作：

  • 移除下划线的字符  s = "aabcbbca"。结果字符串为 s = "abbca"。
  • 移除下划线的字符  s = "abbca"。结果字符串为 s = "ba"。
  • 移除下划线的字符  s = "ba"。结果字符串为 s = ""。

请你返回进行 最后 一次操作 之前 的字符串 s 。在上面的例子中，答案是 "ba"。

 

示例 1：

输入：s = "aabcbbca"
输出："ba"
解释：已经在题目描述中解释。

示例 2：

输入：s = "abcd"
输出："abcd"
解释：我们进行以下操作：
- 删除 s = "abcd" 中加粗加斜字符，得到字符串 s = "" 。
进行最后一次操作之前的字符串为 "abcd" 。

 

提示：

  • 1 <= s.length <= 5 * 105
  • s 只包含小写英文字母。

解法

方法一：哈希表或数组

我们用一个哈希表或数组 $cnt$ 记录字符串 $s$ 中每个字符的出现次数，用一个哈希表或数组 $last$ 记录字符串 $s$ 中每个字符最后一次出现的位置。字符串 $s$ 中出现次数最多的字符的出现次数记为 $mx$。

然后我们遍历字符串 $s$，如果当前字符的出现次数等于 $mx$ 且当前字符所在位置等于该字符最后一次出现的位置，那么我们将当前字符加入答案中。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$，空间复杂度 $O(|\Sigma|)$，其中 $n$ 是字符串 $s$ 的长度，而 $\Sigma$ 是字符集，本题中 $\Sigma$ 为小写英文字母。

Python3

class Solution:
    def lastNonEmptyString(self, s: str) -> str:
        cnt = Counter(s)
        mx = cnt.most_common(1)[0][1]
        last = {c: i for i, c in enumerate(s)}
        return "".join(c for i, c in enumerate(s) if cnt[c] == mx and last[c] == i)

Java

class Solution {
    public String lastNonEmptyString(String s) {
        int[] cnt = new int[26];
        int[] last = new int[26];
        int n = s.length();
        int mx = 0;
        for (int i = 0; i < n; ++i) {
            int c = s.charAt(i) - 'a';
            mx = Math.max(mx, ++cnt[c]);
            last[c] = i;
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            int c = s.charAt(i) - 'a';
            if (cnt[c] == mx && last[c] == i) {
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }
}

C++

class Solution {
public:
    string lastNonEmptyString(string s) {
        int cnt[26]{};
        int last[26]{};
        int n = s.size();
        int mx = 0;
        for (int i = 0; i < n; ++i) {
            int c = s[i] - 'a';
            mx = max(mx, ++cnt[c]);
            last[c] = i;
        }
        string ans;
        for (int i = 0; i < n; ++i) {
            int c = s[i] - 'a';
            if (cnt[c] == mx && last[c] == i) {
                ans.push_back(s[i]);
            }
        }
        return ans;
    }
};

Go

func lastNonEmptyString(s string) string {
	cnt := [26]int{}
	last := [26]int{}
	mx := 0
	for i, c := range s {
		c -= 'a'
		cnt[c]++
		last[c] = i
		mx = max(mx, cnt[c])
	}
	ans := []rune{}
	for i, c := range s {
		if cnt[c-'a'] == mx && last[c-'a'] == i {
			ans = append(ans, c)
		}
	}
	return string(ans)
}

TypeScript

function lastNonEmptyString(s: string): string {
    const cnt: number[] = Array(26).fill(0);
    const last: number[] = Array(26).fill(0);
    const n = s.length;
    let mx = 0;
    for (let i = 0; i < n; ++i) {
        const c = s.charCodeAt(i) - 97;
        mx = Math.max(mx, ++cnt[c]);
        last[c] = i;
    }
    const ans: string[] = [];
    for (let i = 0; i < n; ++i) {
        const c = s.charCodeAt(i) - 97;
        if (cnt[c] === mx && last[c] === i) {
            ans.push(String.fromCharCode(c + 97));
        }
    }
    return ans.join('');
}