C++ 将满足条件的字符串中的字符最大化

在这个问题中，我们需要从字符串中移除最多的字符，条件是相邻字符是前一个字符。

我们可以找到每个字符的出现次数，并检查其相邻字符是否是前一个字符，如果是，则可以移除该字符。

问题陈述-我们有一个包含N个字母字符的字符串。给定的任务是，我们需要移除最多数量的字符，如果字符串中的任何相邻字符是字母表中的前一个字符，则可以移除字符串中的任何字符。最后，打印移除字符的数量。

示例

输入

str = 'acd'

输出

1

解释 - 我们可以移除’d’，因为相邻的字符是’c’。

输入

str = "efghijk"

输出

6

解释 - 我们可以删除’k’，因为相邻字符为’j’。

我们可以删除’j’，因为其相邻字符为’i’。

这样，我们可以删除除了’e’之外的所有字符。所以，我们可以删除6个字符。

输入

str = "agnbpc";

输出

0

解释 – 字符串中的任意字符都没有一个与其前一个字符在字母表中相邻的字符。

方法

这个方法将从 ‘z’ 到 ‘a’ 开始。我们将找到所有出现的 ‘z’、’y’、’x’ 等等。如果我们发现任何字母的前一个相邻字符，则可以删除当前字符。

算法

步骤 1 - 使用循环以逆序遍历字母字符。

步骤 2 - 使用另一个嵌套循环来遍历字符串。如果字符串中的一个字符等于字符 p，则按以下步骤执行。

步骤 3 - 检查是否有任何相邻字符等于前一个字符；如果是，则从字符串中删除该字符，并将 q 的值减少 1。

步骤 4 - 返回更新后的字符串长度减去当前字符串长度的结果。

示例

#include <iostream>
using namespace std;

int numOfMaxCharacters(string alpha, int str_len) {
   // Traverse alphabets from 'z' to 'a'
   for (int p = 'z'; p > 'a'; p--) {
      // Traverse string
      for (int q = 0; q < alpha.size(); q++) {
         // If the character matches
         if (alpha[q] == p) {
            // Check if adjacent characters are less than the current character
            if (alpha[q - 1] == p - 1 || alpha[q + 1] == p - 1) {
               alpha.erase(q, 1);
               q = -1;
            }
         }
      }
   }
   // Return answer
   return str_len - alpha.size();
}
int main() {
   string str = "efghijk";
   // String size
   int str_len = str.size();
   cout << "The number of maximum characters that we can remove is " << numOfMaxCharacters(str, str_len);
}

输出

The number of maximum characters that we can remove is 6

时间复杂度 - O(N)，因为我们遍历字符串。

空间复杂度 - O(1)

在这里，我们按照逆序删除每个字符，以最大化删除次数。如果我们以随机顺序删除字符串中的字符，可能无法达到最大删除字符数。