C++ 通过将前缀增加1来最小化使字符串成为回文的操作

在这个问题中，我们将计算需要增加给定字符串的前缀字符的操作次数。

我们将使用字符差异来计算使字符串成为回文所需的最小操作数量。

问题陈述 -我们给出了一个包含数字数字的字符串nums。我们需要计算将字符串转换为回文所需的最小操作次数。

在一次操作中，我们可以选择字符串的任何前缀，并将所有前缀字符增加1。

示例示例

输入

nums = "22434"

输出结果

2

解释

• 首先，我们可以选择22个前缀并递增所有字符。所以，字符串变成了33434。

• 然后，我们可以选择’3’前缀，字符串变成了43434，这是一个回文字符串。

输入

nums = '151'

输出

0

说明 - 字符串已经是回文字符串。因此，它打印出0。

输入

nums = "32102"

输出

-1

解释 - 通过增加前缀值无法将字符串转换为回文。

方法1

如果字符串满足以下两个条件，我们可以使其成为回文：

• 将字符串分成两个相等的部分后，第一部分的数字应该小于第二部分。

• 左边部分的起始字符应该大于结束字符，因为我们需要选择任何前缀并将每个字符增加1。

算法

步骤1 - 初始化q为len – 1，p为0，因为我们将使用它们作为索引指针。初始化maxOps为最大整数值以存储最小操作数，’curr’初始化为0以存储最大差值。

步骤2 - 开始遍历字符串直到q > p。

步骤3 - 如果索引q处的字符小于索引p处的字符，则返回-1，因为无法将字符串转换为回文。

步骤4 - 将索引q和p处的字符的ASCII值之差存储在’diff’变量中。

步骤5 - 将’curr’和’diff’之间的较大值存储在’curr’变量中。

步骤6 - 如果’maxOps’值小于’diff’，返回-1。

步骤7 - 使用’diff’的值更新’maxOps’。

步骤8 - 将p增加1，将q减少1。

步骤9 - 返回’curr’的值。

示例

#include <bits/stdc++.h>
using namespace std;

int makePalindrome(string alpha, int len) {
   int q = len - 1;
   int p = 0;
   int maxOpes = INT_MAX;
   int curr = 0;
   // Travere from both ends
   while (q > p) {
      // It is not possible to make string palindromic
      if (alpha[q] < alpha[p]) {
         return -1;
      }
      // Get character difference
      int diff = alpha[q] - alpha[p];
      // Get the maximum current difference
      curr = max(curr, diff);
      // At the center side difference should be less than the characters at the end
      if (maxOpes < diff) {
         return -1;
      }
      maxOpes = diff;
      p++;
      q--;
   }
   return curr;
}
int main() {
   string nums = "22434";
   int len = nums.length();
   cout << "The number of minimum operations required to make string palindromic is " << makePalindrome(nums, len);
   return 0;
}

输出

The number of minimum operations required to make string palindromic is 2

时间复杂度 – 对字符串进行遍历的时间复杂度为O(N)。

空间复杂度 – 由于我们没有使用任何额外空间，所以空间复杂度为O(1)。

在这个解决方案中，我们检查从起点到中心的差异，并且如果任何中心侧字符具有更高的差异，则返回-1。程序员可以尝试从中心遍历字符串，并检查起始侧的高差异。