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

在这个问题陈述中，我们的任务是借助 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 to find the longest substring
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]; 
      // condition for checking the character has seen before
      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("The longest substring between same characters: ");
console.log(longSubstr);

复杂度

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

结论

我们已经了解了如何使用 Javascript 函数来识别两个相同字符之间的最长子字符串。此外，我们上面实现的方法有效地从输入字符串中获取子字符串。

更新于: 2023年5月18日

417 次查看

启动您的 职业生涯

通过完成课程获得认证

开始
广告