C++ 最小字符数以使字符串组合成长度为K的回文字符串

在字符串控制领域，追踪最小个数的字符应该被改变以将给定字符串转换为K长度的回文子字符串是一个常见的问题。一个从前往后读和从后往前读都相同的字符串称为回文字符串。例如，”radar”或”level”。本文将涵盖用于有效解决此问题的基本概念、方法和潜在优化策略。通过本文的阅读，读者将能够处理类似的字符串操作问题，因为他们将全面了解所需的步骤。

该问题将在下文中完整解释，然后将讨论每种方法的优缺点。选择的方法将进行彻底的检查，并提供代码示例以展示如何使用它们。我们还将研究每种方法的时间复杂度，以了解在各种输入数量下它有多么有效。

使用的方法

暴力法
滑动窗口法

暴力法

找到最少字符数以组成一个长度为K的回文字符串的暴力方法是在给定字符串中检查长度为K的所有可能子字符串。其步骤如下：设置两个指针，left和right，将它们初始化为K字符子字符串的起始和结束位置，并初始化一个变量来跟踪最少的替换次数，然后迭代字符串，每次迭代时将窗口更新为正确移动一步。对于每个窗口，通过比较左右字符来检查它是否可能是一个回文字符串，如果不是一个回文字符串，则计算所需的替换次数。记录目前为止找到的最少替换次数。一直进行此训练直到字符串结束。结果将是实现指定的长度为K的回文子字符串所需的最少替换次数。然而，该方法的时间复杂度较高，对于大型字符串来说效率低下。

步骤

遍历给定的字符串时，将每个长度为K的子字符串考虑为一个遍历的元素。
验证每个子字符串是否为回文字符串。
计算如果子字符串不是回文字符串，则需要更改的字符数量。
保持具有最少替换次数的子字符串。
通过更改最少替换子字符串中的字符来生成回文字符串。

示例

#include <iostream>
#include <string>
using namespace std;

string minimalReplacementPalindromeSubstring(const string& str, int K) {
   int n = str.length();
   string minReplacementSubstr;

   for (int i = 0; i <= n - K; i++) {
      string substr = str.substr(i, K);
      int replacements = 0;
      for (int j = 0; j < K / 2; j++) {
         if (substr[j] != substr[K - 1 - j]) {
            replacements++;
         }
      }

      if (replacements < minReplacementSubstr.length() || minReplacementSubstr.empty()) {
         minReplacementSubstr = substr;
      }
   }

   return minReplacementSubstr;
}

int main() {
   string input = "iurefhuhfrati";
   int K = 4;

   string result = minimalReplacementPalindromeSubstring(input, K);
   cout << "Minimal Replacement Substring: " << result << endl;

   return 0;
}

输出

Minimal Replacement Substring: rati

滑动窗口方法

滑动窗口方法是一种有效解决问题的方法，包括子数组或子字符串操作。在找到替换最少字符以创建长度为K的回文字符串串联的情况下，该方法在导航输入字符串时将维持一个固定大小为K的窗口（子字符串）。

算法在开始时设置两个指针’left’和’right’，分别指示K个字符的子串的开始和结束。接着，它确定将该子串转换为回文所需的替换次数。为了追踪所需的最少替换次数，初始化一个变量’min_replacements’。

步骤

设置两个指针left和right，分别指向第一个K个字符子串的开始和结束。
确定将子串转换为回文所需的替换次数。
为了追踪所需的最少替换次数，初始化变量min_replacements。
通过将right指针向右移动一个位置来更新窗口。
如果当前窗口是回文，则移动right指针。
计算所需的替换次数，并在当前窗口不是回文时，如有必要，则更改min_replacements。
为了更新窗口，将left指针向右移动一个位置。
重复步骤4到7，直到字符串结束。
子串的字符应该用最少的替换次数进行替换。

示例

#include <iostream>
#include <string>
using namespace std;

int minReplacementsForPalindrome(string s, int k) {
   int left = 0, right = k - 1, min_replacements = 0;
   while (right < s.length()) {
      int i = left, j = right;
      while (i < j) {
         if (s[i] != s[j])
            min_replacements++;
         i++;
         j--;
      }
      left++;
      right++;
   }
   return min_replacements;
}

int main() {
   string input_string = "abcxyzuvw"; // Replace this with your desired input string
   int k = 3; // Replace this with the desired value of K
   int result = minReplacementsForPalindrome(input_string, k);
   cout << "Minimum replacements required: " << result << endl;
   return 0;
}