C++ 最多花费T的情况下，可以将A的最长子字符串更改为B的子字符串

在这个问题中，我们将找到A的最长子字符串，将其转换为B的子字符串，从相同索引开始，在不超过T的成本的情况下。

我们将使用二分搜索算法来找到满足给定条件的子字符串的最大长度。然而，解决这个问题的朴素方法是找到满足问题陈述中条件的所有子字符串，并取长度最长的子字符串。

问题陈述 - 我们给出了长度为N的字符串A和B。此外，我们还给出了总成本’T’。K是将一个字符转换为另一个字符的成本。

我们需要找到A字符串的最长子字符串，使得我们可以将其与B字符串中以相同索引开始的子字符串相同，并且将一个子字符串转换为另一个的总成本不应超过T。同时，打印这样子字符串的起始和结束索引。

示例示例

输入

A = "wxyz", B = "wpqt"; K = 2, T = 5;

输出：

Starting index – 0, ending index - 2

解释

我们可以将”wxy”转换为”wpq”，成本为4，小于5。

输入

A = "wxyz", B = "ewrt"; K = 6, T = 5;

输出

‘Not possible.’

说明

在这里，K大于T，并且没有子字符串从相同的索引开始相同。因此，不可能找到这些子字符串。

输入

A = "pqdetr", B = "tqcets"; K = 1, T = 5;

输出

Starting index – 0, ending index - 5

解释

我们可以将字符串A作为子字符串，因为其5个字符是不同的，我们可以通过代价为5将其与字符串B相同。

方法1

在这个方法中，我们将使用二分搜索算法来解决这个问题。我们将检查是否存在一个有效的子字符串长度为“中间长度”。如果是，则我们将在范围[mid，字符串长度]内找到有效的子字符串长度。否则，我们将在[0，mid]内找到有效的字符串长度。

我们将使用滑动窗口技术来找到特定长度的有效子字符串。

算法

步骤 1 - 使用 -1 初始化 st_ind 和 end_ind 变量，用于存储最大长度子字符串的起始和结束索引。
步骤 2 - 将 ‘left’ 指针初始化为 0，’right’ 初始化为字符串长度 + 1。此外，将 ‘maxLen’ 初始化为 0，用于存储子字符串的最大长度。
步骤 3 - 现在，我们需要使用二分搜索技术。因此，使用 while 循环开始迭代，直到左指针的值小于右指针的值。
步骤 4 - 通过将左指针和右指针之和除以 2，找到中间长度。
步骤 5 - 执行 isMidValid() 函数，检查是否存在长度等于 ‘中间长度’ 的子字符串。
第5.1步 - 在isMidValid（）函数中，使用0初始化“p”和“q”变量作为滑动窗口指针。同时，使用0初始化“ct”变量，以存储当前窗口的成本，使其与字符串B的子字符串相同。
第5.2步 - 使用false初始化“isValid”变量，以跟踪是否存在有效的子字符串。
第5.3步 - 使用循环进行迭代，直到“q”小于字符串A的长度为止。在循环中，如果A[q]和B[q]不相同，则将将一个字符转换为另一个字符的成本K添加到“ct”中。
第5.4步 - 如果当前窗口的长度等于“midLen”，执行以下步骤。
第5.4.1步 - 如果‘ct’小于T，则将‘isValid’设置为true，将‘st_ind’更新为p，将‘end_ind’更新为q。
Step 5.4.2 - 要移动到下一个长度为‘midLen’的窗口，从‘ct’中删除‘A[p]’的成本，并将‘p’的值增加1。
Step 5.5 - 将‘q’的值增加1。
Step 5.6 - 返回‘isValid’变量的值。
Step 6 - 如果函数返回true，则更新‘maxLen’并在右半部分搜索最大长度。否则，在左半部分搜索最大长度。
Step 7 - 最后，如果‘st_ind’的值为-1，则子字符串不可能。否则，打印最长有效子字符串的起始和结束索引。

示例

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

// Starting and ending position of valid substring
int st_ind = -1, end_ind = -1;
bool isMidValid(int midLen, string &A, string &B, int K, int T) {
   int p = 0, q = 0, len = A.size(), ct = 0;
   // To track whether any substring of length MidLen is valid
   bool isValid = false;
   while (q < len) {

      // Cost for converting one character to other
      ct += ((A[q] != B[q]) ? K : 0);

      // Shifting the window to right
      if (q - p + 1 == midLen) {

         // For cost less than T
         if (ct <= T) {
            isValid = true;
            st_ind = p;
            end_ind = q;
         }

         // Removing left character from window
         ct -= ((A[p] != B[p]) ? K : 0);
         p++;
      }
      q++;
   }

   // output
   return isValid;
}
void printLongestSubstr(string A, string B, int K, int T) {
   st_ind = -1, end_ind = -1;

   // Left and right pointers for binary search
   int left = 0;
   int right = A.size() + 1;
   int len = A.size();

   // To store the maximum length
   int maxLen = 0;
   while (left < right) {

      // Mid calculation
      int midLen = (left + right) / 2;

      // If midLen length is valid
      if (isMidValid(midLen, A, B, K, T)) {

         // Update max length
         maxLen = midLen;

         // Find the maximum length in the right half
         left = midLen + 1;
      } else {

         // If mid is invalid, then find in the left half
         right = midLen;
      }
   }
   if (st_ind == -1)
      cout << "Not possible\n";
   else
      cout << "Starting index - " << st_ind << " ending index - " << end_ind << "\n";
}
int main() {
   string A = "wxyz", B = "wpqt";
   int K = 2, T = 5;
   printLongestSubstr(A, B, K, T);
   return 0;
}