删除字符串中出现次数最少的字符

当我们处理字符串时，有时候需要找出出现次数最少的字符并将其从字符串中删除。这个问题在实际开发中经常会遇到，因此本篇文章将从多个角度分析如何解决这个问题。

方法一：哈希表

我们可以使用哈希表来记录每个字符出现的次数，然后再遍历一遍字符串，找出出现次数最少的字符并将其删除。

具体实现步骤如下：

1. 遍历字符串，将每个字符出现的次数记录在哈希表中。

2. 遍历哈希表，找出出现次数最少的字符。

3. 遍历字符串，删除出现次数最少的字符。

代码示例：

```

void deleteLeastAppearingChar(string &str) {

unordered_map m;

int least = INT_MAX;

for (char c : str) {

m[c]++;

}

for (auto p : m) {

least = min(least, p.second);

}

for (int i = 0; i < str.size(); i++) {

if (m[str[i]] == least) {

str.erase(i, 1);

i--;

}

}

}

```

时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 为字符串的长度。

方法二：桶排序

由于哈希表的空间复杂度比较高，我们可以使用桶排序来优化空间复杂度。

具体实现步骤如下：

1. 遍历字符串，将每个字符出现的次数记录在桶中。

2. 遍历桶，找出出现次数最少的字符。

3. 遍历字符串，删除出现次数最少的字符。

代码示例：

```

void deleteLeastAppearingChar(string &str) {

vector bucket(256, 0);

int least = INT_MAX;

for (char c : str) {

bucket[c]++;

}

for (int num : bucket) {

if (num > 0 && num < least) {

least = num;

}

}

for (int i = 0; i < str.size(); i++) {

if (bucket[str[i]] == least) {

str.erase(i, 1);

i--;

}

}

}

```

时间复杂度为 O(n)，空间复杂度为 O(1)，其中 n 为字符串的长度。

方法三：双指针

我们也可以使用双指针来解决这个问题。具体实现步骤如下：

1. 遍历字符串，将每个字符出现的次数记录在数组中。

2. 使用双指针 i 和 j 遍历字符串，当 s[j] 出现次数等于最小值时，j 向右移动。

3. 当 s[j] 出现次数大于最小值时，将 s[i] 替换为 s[j]，同时将数组中 s[i] 和 s[j] 出现次数交换，并将 i 向右移动。

4. 当 j 遍历完整个字符串后，将字符串截取为前 i 个字符。

代码示例：

```

void deleteLeastAppearingChar(string &str) {

int counts[256] = {0};

for (char c : str) {

counts[c]++;

}

int i = 0, j = 0, least = INT_MAX;

while (j < str.size()) {

if (counts[str[j]] == least) {

j++;

} else if (counts[str[j]] > least) {

str[i++] = str[j];

swap(counts[str[i - 1]], counts[str[j]]);

} else {

least = counts[str[j]];

j++;

}

}

str = str.substr(0, i);

}

```

时间复杂度为 O(n)，空间复杂度为 O(1)，其中 n 为字符串的长度。

方法四：STL

最简单的方法是使用STL中的 sort、lambda 和 erase_if 函数。

代码示例：

```

void deleteLeastAppearingChar(string &str) {

unordered_map m;

for (char c : str) {

m[c]++;

}

auto it = min_element(m.begin(), m.end(),

[](const pair & a, const pair & b) {

return a.second < b.second;

});

str.erase(remove_if(str.begin(), str.end(),

[&](const char& c) {

return m[c] == it->second;

}),

str.end());

}

```

时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为字符串的长度。