查找两个相同字符之间的最长子字符串 JavaScript

javascriptweb developmentfront end technology

在此问题陈述中，我们的任务是借助 Javascript 功能查找两个相同字符之间的最长子字符串。此任务可以借助 map 函数来完成，以跟踪两个相同的字符。

给定问题的逻辑

问题陈述我们必须在给定字符串中找到两个相同字符之间的最长子字符串。例如，如果我们有一个像"abcdefa"这样的字符串，则有两个相同的字符"a"，它们有 5 个字符，称为"bcdef"，因此这将被称为最长子字符串。为了实现上述问题，我们将使用 map 方法来跟踪第一个和最后一个相同的字符，然后显示相同字符之间的子字符串的输出，

算法

步骤 1 - 通过定义函数 longestSubstring 并传递参数"str"来启动程序。

步骤 2 - 之后，我们将声明名为 maxLength 和 begin 的变量，分别用 0 和 -1 初始化这些变量。

步骤 3 - 现在，我们将借助 Map 函数和 new 关键字创建一个名为 charMap 的映射。

步骤 4 - 在此步骤中，我们将启动一个 for 循环并运行此循环直到字符串 str 的长度。

步骤 5 - 完成上述所有步骤后，创建另一个变量以从字符串中获取每个字符的详细信息并检查条件。

步骤6 − 当我们获得 char 变量中的每个字符时，是时候检查该字符是否以前出现过。如果给定条件为真，则将其添加到上一个索引值中。

步骤 7 − 检查完上述所有条件后，我们将获得属于字符串中相同字符之间的子字符串，并将输出显示到控制台。

算法代码

//函数用于查找最长子字符串
function longestSubstring(str) {
   let maxLength = 0;
   let begin = -1;
   let charMap = new Map();
   for (let i = 0; i < str.length; i++) {
      const char = str[i]; 
      // 检查角色之前是否见过的条件
      if (charMap.has(char)) {
         const previousIndex = charMap.get(char);
         const len = i - previousIndex - 1;
         if (len > maxLength) {
            maxLength = len;
            begin = previousIndex + 1;
         }
      } else {
         charMap.set(char, i);
      }
   }
   if (begin === -1) {
      return "";
   }
   return str.substring(begin, begin + maxLength);
}
const str = "abcaabcdaaaefghij";
const longSubstr = longestSubstring(str);
console.log("相同字符之间最长的子字符串: ");
console.log(longSubstr);

复杂度

假设 n 是输入字符串 str 的长度，因此执行上述函数所需的时间为 O(n)。因为该函数只对字符串进行一次迭代，并处理每个字符的常量时间操作。假设 m 是输入字符串中相同字符之间的字符数，因此代码的空间复杂度为 O(m)。因为代码使用 map 函数来存储每个字符出现的索引，并且该索引的大小等于唯一字符的大小。