最小的子串需要被删除才能使给定的字符串成为回文

回文是一种正向和反向读取都相同的字符序列。在计算机科学和编程中，回文是字符串操作问题中常见的主题。在本文中，我们将探讨如何找到必须从给定字符串中删除的最小大小的子串，使其成为回文。我们将提供一个结构良好的C++解决方案，并包含一个示例来说明测试用例。

问题陈述

给定长度为'n'的字符串's'，我们需要找到应该删除的子字符串的最小大小，以使剩下的字符串成为回文。

算法

• 创建一个名为isPalindrome的函数，它以字符串's'作为参数，并在其为回文时返回true，否则返回false。

• 创建一个名为minSizeSubstringToRemove的函数，它以字符串's'作为参数。

• 将变量'minSize'初始化为字符串的长度。

• 使用循环迭代字符串，从0到'n'递增一个索引'i'。

• 在每次迭代中，执行以下步骤 −

• 从字符串的开头到索引'i'创建两个子字符串，另一个从索引'i'到字符串的末尾。

• 检查其中任意一个子字符串是否为回文。

• 如果任一子字符串是回文，将'minSize'更新为非回文子字符串的长度和'minSize'之间的最小值。

• 将'minSize'作为结果返回。

示例

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

// Function to check if a string is a palindrome
bool isPalindrome(const std::string &s) {
   int left = 0;
   int right = s.length() - 1;
   
   while (left < right) {
      if (s[left] != s[right]) {
         return false;
      }
      ++left;
      --right;
   }
   
   return true;
}

// Function to find the minimum size substring to be removed
int minSizeSubstringToRemove(std::string s) {
   int n = s.length();
   int minSize = n;
   
   for (int i = 0; i <= n; ++i) {
      std::string leftSubstring = s.substr(0, i);
      std::string rightSubstring = s.substr(i, n - i);
   
      if (isPalindrome(leftSubstring)) {
         minSize = std::min(minSize, static_cast<int>(rightSubstring.length()));
      }
      if (isPalindrome(rightSubstring)) {
         minSize = std::min(minSize, static_cast<int>(leftSubstring.length()));
      }
   }
   
   return minSize;
}

int main() {
   std::string s = "abccbaab";
   int result = minSizeSubstringToRemove(s);
   std::cout << "Minimum size substring to be removed: " << result << std::endl;
   
   return 0;
}

输出

Minimum size substring to be removed: 2

测试用例示例

考虑以下字符串："abccbaab"。可能的子字符串及其对应的回文状态如下：

• 左子字符串 = ""，右子字符串 = "abccbaab"，回文 = false

• 左子串 = "a"，右子串 = "bccbaab"，回文 = false

• 左子串 = "ab"，右子串 = "ccbaab"，回文 = false

• 左子串 = "abc"，右子串 = "cbaab"，回文 = false

• 左子串 = "abcc"，右子串 = "baab"，回文 = false

• 左子串 = "abccb"，右子串 = "aab"，回文 = true（左子串）

• 左子字符串 = "abccba"，右子字符串 = "ab"，回文 = true（左子字符串）

• 左子字符串 = "abccbaa"，右子字符串 = "b"，回文 = false

• 左子串 = "abccbaab"，右子串 = ""，回文 = false

从上面的迭代中，我们可以看到，要删除的最小大小的子字符串是2，当左子字符串是"abccba"，右子字符串是"ab"时发生。在这种情况下，删除右子字符串"ab"将使剩余的字符串"abccba"成为回文。

结论

在本文中，我们探讨了寻找最小大小子串的问题，该子串必须被删除以使给定字符串成为回文。我们提供了一个清晰高效的C++实现，利用一个简单的循环来遍历字符串，创建子串并检查它们的回文状态，以找到必须被删除的子串的最小大小。

通过理解这个算法，你可以将类似的概念应用于解决计算机科学和编程中的其他字符串操作和回文问题。