在给定条件下最大化从字符串中删除的字符数

在这个问题中，我们需要删除字符串中的最大字符数，如果相邻字符是前一个字符。

我们可以找到每个字符的出现次数，并检查其任何相邻字符是否为前一个字符，我们可以删除该特定字符。

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

示例

输入

str = 'acd'

输出

1

解释 - 我们可以删除 'd'，因为相邻字符是 'c'。

输入

str = "efghijk"

输出

6

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

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

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

输入

str = "agnbpc";

输出

0

解释 - 字符串的任何字符都没有相邻字符是字母表中的前一个字符。

方法 1

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

算法

步骤 1 - 使用循环反向遍历字母字符。

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

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

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

示例

Open Compiler
#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)

在这里，我们以反向顺序删除每个字符以最大化删除。如果我们以随机顺序从字符串中删除字符，我们可能无法删除最大字符。

更新于：2023年8月24日

83 次查看

开启你的职业生涯

完成课程获得认证

开始
广告