给定字符串S中存在的子序列T的最大相邻索引差

---

在这个问题中，我们需要找到给定字符串中存在的子序列的索引之间的最大差值。

为了解决这个问题，我们需要找到子序列在实际顺序和反向顺序中的索引。之后，我们需要取两者的差值。

问题陈述 - 我们给定两个名为“str”和“sub”的字符串。“sub”字符串始终作为子序列存在于“str”字符串中。我们需要找到最大索引成本。索引成本是子序列的两个索引之间的差值。

示例

输入

str = "deeer", sub = "der"

输出

3

解释

• 我们可以使用{0, 1, 4}、{0, 2, 4}和{0, 3, 4}来获取“sub”。

• 因此，如果我们取集合{0, 1, 4}，我们可以得到最大相邻索引差，即4 - 1 == 3。

输入

str = "abcdef", sub = "acf"

输出

3

解释

• 子序列存在于{0, 2, 5}索引处。因此，索引之间的最大差值为5 - 2 = 3。

输入

str = "bbbbbbb", sub = "bb";

输出

6

解释 - 我们可以取子序列的{0, 6}索引来获得相邻索引之间的最大差值。

方法1

在这种方法中，我们将按照实际顺序查找子序列索引。之后，我们将按照反向顺序查找子序列索引。我们将从反向索引中减去实际索引以获得最大差值。

让我们通过下面的例子来理解这种方法。

str = "bbbbbbb", sub = "bbb";

• 当我们按照实际顺序查找子序列索引时，我们将得到{0, 1, 2}索引。

• 当我们按照反向顺序查找子序列索引时，我们将得到{4, 5, 6}。

• 最后，我们将减去reverse[p + 1] - actual[p] = 6 - 1 = 5。同样，5 - 0 = 5。这样，我们可以得到最大相邻索引差。

算法

步骤1 - 定义'max_diff'变量来存储最大相邻索引差。另外，定义长度等于子字符串长度的leftInd和rightInd数组来存储子序列的索引，分别从左到右。

步骤2 - 开始遍历给定的字符串。如果指向“sub”字符串的指针大于字符串长度，则中断循环。

步骤3 - 如果字符串中第p个索引处的字符和“sub”字符串中sub_ind索引处的字符相同，则将p值赋给“leftInd”数组并递增sub_ind指针。

步骤4 - 将sub_ind指针初始化为子字符串长度 - 1，并开始反向遍历字符串。

步骤5 - 如果sub_ind小于0，则中断循环。此外，如果字符串的字符和“sub”匹配，则更新“rightInd”数组并将“sub_ind”值减1。

步骤6 - 遍历“leftInd”和“rightInd”数组。如果rightInd[p + 1] - leftInd[p]大于它，则更新maxDiff变量的值。

步骤7 - 返回“maxDiff”值。

示例

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

int findMaxIndexDiff(string str, string sub, int str_len, int sub_len) {
   // to store maximum index difference
   int maxDiff = 0;
   // to store minimum and maximum possible values of the character index
   int leftInd[sub_len], rightInd[sub_len];

   // pointer for substring
   int sub_ind = 0;
   // traverse the string
   for (int p = 0; p < str_len; p++) {
      if (sub_ind >= sub_len)
         break;
// store the left-most index of the character of a substring in the given string
      if (str[p] == sub[sub_ind]) {
         leftInd[sub_ind] = p;
         sub_ind++;
      }
   }
   sub_ind = sub_len - 1;
   for (int p = str_len - 1; p >= 0; p--) {
      if (sub_ind < 0)
         break;
      // Storing right-most index of character
      if (str[p] == sub[sub_ind]) {
         rightInd[sub_ind] = p;
         sub_ind--;
      }
   }
   for (int p = 0; p < sub_len - 1; p++){
      // Getting the maximum difference
      maxDiff = max(maxDiff, rightInd[p + 1] - leftInd[p]);
   }
   // Return the final answer
   return maxDiff;
}
int main() {
   string str = "deeer", sub = "der";
   int str_len = str.length(), sub_len = sub.length();
   cout << "The maximum index difference for a subsequence present in the given string is " << findMaxIndexDiff(str, sub, str_len, sub_len);
   return 0;
}

输出

The maximum index difference for a subsequence present in the given string is 3

时间复杂度 - O(n + m) 用于遍历字符串和子序列索引数组。

空间复杂度 - O(M) 用于存储子序列的索引。

我们可以取子序列的任何出现并找到其相邻索引之间的最大差值。程序员应该使用不同的输入测试代码，以便更好地理解问题及其解决方案。