C++ 最少需要进行删除操作使得给定的字符串只由一对交替字符组成

题目背景

计算机科学中经常会遇到一种常见问题，即需要最小的删除操作来使给定的字符串只包含一对交替字符。在涉及字符串操作的应用中，经常会遇到这个问题。

在本教程中，我们将使用C ++编程语言解决这个问题。我们将从详细解释问题陈述开始，并讨论它在各种现实世界应用中的重要性。

然后，我们将提供逐步算法来解决这个问题，并展示其在C ++中的实现。最后，我们将总结我们解决方案的时间和空间复杂性，并讨论改进的潜在领域。所以让我们开始吧！ < /p>

问题陈述

此程序的目标是找到需要从给定字符串’S’中删除的最小字符数，以将其转换为只有两个交替字符的新字符串。

示例1

输入

String S = "abccd"

输出结果

说明：从原始字符串中消除所有的 ‘c’ 和 ‘d’ 之后，我们得到了结果字符串 “ab”，它的特点是 ‘a’ 和 ‘b’ 交替出现的模式。

示例示例 2

输入

String S = "adebbeeaebd"

输出

说明：在消除所有的’b’和’e’后，我们得到字符串“adad”，它展示了’a’和’d’之间交替出现的模式。

算法

步骤1. 定义一个名为’findLength’的函数，它接受三个参数：一个字符串’s’，和两个字符’i’和’j’。

步骤2. 在’findLength’函数内部：

初始化一个变量’required’为’i’。
初始化一个变量’length’为0，用于跟踪字符的数量。
迭代字符串’s’中的每个字符’curr’。
- 如果当前字符’curr’等于所需字符’required’：
  - 将’length’增加1。
  - 如果’required’当前为’i’，则将’required’更新为另一个字符（’j’）；如果’required’当前为’j’，则将’required’更新为’i’。这样可以保证交替字符。
返回最终的长度。

步骤3. 定义一个名为’minimumDeletions’的函数，它接受一个字符串’S’作为参数。

步骤4. 在’minimumDeletions’函数内部：

初始化一个变量’len’为0，用于存储找到的交替字符的最大长度。
获取字符串’S’的长度，并将其存储在变量’n’中。
使用变量’i’迭代从’a’到’z’的所有小写字母。
- 对于每个’i’，使用变量’j’迭代从’i + 1’到’z’的所有后续小写字母。
- 调用’findLength’函数，参数为’S’、’i’和’j’，以获取考虑’i’和’j’时的交替字符的长度。
- 将’len’更新为’len’和新获取的长度之间的最大值。
通过将输入字符串长度’n’减去’len’来计算所需的最小删除数量。
返回最小删除数量。

步骤5. 在主函数内部：

创建一个字符串’S’并将其初始化为”abccd”。
调用’minimumDeletions’函数，参数为’S’，并将结果存储在一个变量中。
使用’std::cout’输出结果。

注意：上述算法假设输入字符串’S’仅包含小写英文字母。如果输入字符串包含其他字符或大写字母，则程序可能无法按预期工作。

示例

使用C++实现上述算法

以下C++程序确定从字符串中删除的最小字符数，以便获得仅由两个交替字符组成的字符串。

‘findLength’函数使用两个字符作为交替标记，在给定的字符串中计算交替子字符串的长度。

‘minimumDeletions’函数遍历所有可能的字符对（’a’到’z’），并使用‘findLength’函数找到最大的交替子字符串长度。

程序的‘main’函数将字符串‘S’初始化为”abccd”，并调用‘minimumDeletions’来计算结果。然后使用‘cout’打印结果。

整个程序有效地解决了找到所需的最小删除次数以获得只有两个交替字符的字符串的问题。

#include <iostream>
#include <string>
#include <algorithm>

int findLength(std::string s, char i, char j) {
   char required = i;
   int length = 0;
   for (char curr : s) {
      if (curr == required) {
         length += 1;
         required = (required == i) ? j : i;
      }
   }
   return length;
}
int minimumDeletions(std::string S) {
   int len = 0;
   int n = S.length();
   for (char i = 'a'; i <= 'z'; i++) {
      for (char j = i + 1; j <= 'z'; j++) {
         int newLen = findLength(S, i, j);
         len = std::max(len, newLen);
      }
   }
   return n - len;
}
int main() {
   std::string S = "abccd";
   std::cout << minimumDeletions(S) << std::endl;
   return 0;
}

输出

结论

总之，提供的C++程序有效地解决了确定将给定字符串转换为仅由一对交替字符组成的新字符串所需的最小字符删除数量的问题。通过利用findLength函数来识别交替子字符串的长度和minimumDeletions函数来找到最大交替子字符串长度，该程序成功地计算出所需的结果。该解决方案使得能够有效处理需要进行最小字符删除以实现所需的交替字符模式的情况。