通过替换 Q 查询中的 K 个字符来检查子字符串是否为回文

是的，它可以通过替换字符成为回文字符串。替换 2 个字符后的回文字符串为 'indni'。

语法

• length() - 它是在 <string> 头文件中定义的字符串类库函数。它返回字符串的长度。字符串的长度就是字符串的字符数。

string_name.length();

• vector − 它是 C++ 中用于存储元素的容器。它是一个动态数组，不受数组大小限制。它具有不同的数据类型。

vector<data_type> vector_name;

• vector<vector<> − 它是 vector 中的 vector，一个二维 vector。其工作原理类似于普通 vector。每一行都是一个向量。

vector<vector<data_type> > vector_name;

算法

• 初始化字符串 s。

• 使用数字数组初始化查询。

• 使用循环迭代字符串字符。

• 创建一个 2d 向量，用于存储使用查询的起始和结束索引值生成的子字符串。

• 使用子字符串处理查询并计算不匹配的字符。

• 使用剩余字符转换一半不匹配的字符。

• 如果更改的字符数等于或小于 k 的值，则输出为 Yes。

• 如果替换的字符数大于 K 的值，则打印 No。

• 处理所有查询。

示例 1

我们使用 C++ 中的动态规划实现了其中一个演示。动态规划降低了时间复杂度，并且不会多次执行相同的步骤。它将任务分成几部分并使用递归。

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

//用户定义函数从生成的子字符串中找出回文字符串
void findPalindrome(string s, vector<vector<int> >& Q){
   int l = s.length();
   vector<vector<int> > dpa(26, vector<int>(l, 0));  // 二维数组存储字符数
   
   //迭代字符串以生成子字符串
   for (int x = 0; x < 26; x++)  {
      char currentCharVal= x + 'a';     // 当前字符的值
      for (int y = 0; y < l; y++) {
         // 使用计数器字符的新值更新 dp 数组
         if (y == 0)  {
            dpa[x][y] = (s[y] == currentCharVal); }
         else {
            dpa[x][y] = dpa[x][y - 1] + (s[y] == currentCharVal); 
         }
      }
   }
   
   // 处理查询
   for (auto query : Q) {
      int leftInd = query[0];
      int rightInd = query[1];
      int k = query[2];
      int unMatched = 0;      // 查找并存储不匹配的字符
      for (int x = 0; x < 26; x++){
         int cnt = dpa[x][rightInd] - dpa[x][leftInd] + (s[leftInd] == (x + 'a'));
         if (cnt & 1)
            unMatched++;  
      }
      int result = unMatched / 2; // 初始化结果变量的值
      
      // 定义输出条件
      if (result <= k) {cout << "YES\n"; }
      else {cout << "NO\n"; }
   }
}
int main() {
   string s = "helloindia";
   vector<vector<int> > Q;  // 初始化查询
   Q = { { 1, 4, 0 }, {1, 4, 2 }, { 6, 9, 2 }, { 3, 8, 4 }};
   
   // 调用函数来处理查询并生成子字符串
   findPalindrome(s, Q);
   return 0; 
}

输出

NO
YES
YES
YES

示例 2

我们可以不使用动态规划来实现本教程中的问题陈述。为了生成子字符串并处理查询，使用了循环。使用"changes"变量计算已更改的字符数。当更改数小于或等于 K 时，输出为 Yes，否则输出为 No。

使用 auto 自动定义变量的数据类型。

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

// 生成子字符串并处理查询以检查子字符串是否为回文的函数
void checkPalindrome(string s, vector<vector<int>>& Q)  {
   //处理查询
   for (auto query : Q)   {
      int leftVal = query[0];
      int rightVal = query[1];
      int k = query[2];
      int l = rightVal - leftVal + 1;
      int unmatchedCnt = 0;
      //用于存储字符值的向量
      vector<int> cnt(26, 0);
      //生成子字符串
      for (int x = leftVal; x <= rightVal; x++)
         cnt[s[x] - 'a']++;
      for (int x = 0; x < 26; x++)  {
         if (cnt[x] % 2 != 0)
            unmatchedCnt++; 
      }
      int changes = unmatchedCnt / 2;
      // 输出条件
      if (changes <= k) 
         cout << "YES\n";
      else{ 
         cout << "NO\n";  
      }
   }
}

//代码控制器
int main()  {
   string s = "helloindia";
   vector<vector<int>> Q = { { 1, 4, 0 }, {1, 4, 2 }, { 6, 9, 2 }, { 3, 8, 4 }};
   checkPalindrome(s, Q);
   return 0;
}

输出

NO
YES
YES
YES

结论

我们已经到了本教程的结尾。在本教程中，我们考虑一个字符串并通过查询生成子字符串。我们通过替换最多 K 个字符来检查子字符串是否可以是回文字符串。K 是将子字符串转换为回文字符串时替换的最大字符数。为了在 C++ 中实现该任务，我们使用了循环和动态规划。在本教程中，我们使用了一个二维向量来存储查询。

相关文章

• 图中的团
• 无权图的应用、优点和缺点
• 计算给定数字字符串连接 K 次后生成的字符串中 01 的子序列
• String 可以被视为关键字吗?
• 通过将辅音替换为最接近的元音或将辅音替换为最接近的元音来计算唯一字符串的数量
• 通过替换 Q 查询中的 K 个字符来检查子字符串是否为回文
• 检查字符串是否可以使用 Qwerty 键盘的同一行打印
• 计算所有子字符串的权重和最多为 K
• 中心十八边形数
• 中心八边形数