首页 > 编程语言 >LeetCode 无重复字符的最长子串算法题解 All In One

LeetCode 无重复字符的最长子串算法题解 All In One

时间:2022-10-01 09:22:13浏览次数:76  
标签:子串 题解 maxStr maxLen let result https com LeetCode

LeetCode 无重复字符的最长子串算法题解 All In One

js / ts 实现无重复字符的最长子串

无重复字符的最长子串原理 图解

滑动窗口


"use strict";

/**
 *
 * @author xgqfrms
 * @license MIT
 * @copyright xgqfrms
 * @created 2022-09-30
 * @modified
 *
 * @description 3. 无重复字符的最长子串
 * @description 3. Longest Substring Without Repeating Characters
 * @difficulty Medium
 * @ime_complexity O(n)
 * @space_complexity O(1)
 * @augments
 * @example
 * @link https://leetcode.com/problems/longest-substring-without-repeating-characters/
 * @link https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * @solutions
 *
 * @best_solutions
 *
 */

export {
  lengthOfLongestSubstring,
};

const log = console.log;


function lengthOfLongestSubstring(str: string): number {
  let maxStr = ``;
  let maxLen = 0;
  for(const c of str) {
    let index = maxStr.indexOf(c);
    if(index > -1) {
      // slice + 1,截取当前字符后面的字符串
      // slice +1 从下一个字符开始截取
      maxStr = maxStr.slice(index + 1);
    }
    maxStr += c;
    if(maxLen < maxStr.length) {
      // 更新最长字符串
      maxLen = maxStr.length;
    }
    // maxLen = Math.max(maxLen, maxStr.length);
  }
  return maxLen;
}

function getMaxSubStr(str: string): string {
  let result = ``;
  let maxStr = ``;
  let maxLen = 0;
  for(const c of str) {
    let index = maxStr.indexOf(c);
    if(index > -1) {
      // slice + 1,截取当前字符后面的字符串
      maxStr = maxStr.slice(index + 1);
    }
    maxStr += c;
    if(maxLen < maxStr.length) {
      maxLen = maxStr.length;
      result = maxStr;
    }
  }
  return result;
}

function getMaxSubStrObj(str: string): Object {
  let result = ``;
  let maxStr = ``;
  let maxLen = 0;
  for(const c of str) {
    let index = maxStr.indexOf(c);
    if(index > -1) {
      // slice + 1,截取当前字符后面的字符串
      maxStr = maxStr.slice(index + 1);
    }
    maxStr += c;
    if(maxLen < maxStr.length) {
      maxLen = maxStr.length;
      result = maxStr;
    }
  }
  return {
    maxStr: result,
    maxLen
  };
}


/*

"abcabcbb"
"bbbbb"
"pwwkew"

*/

// 测试用例 test cases
const testCases = [
  {
    input: "abcabcbb",
    result: 3,
    desc: 'value equal to 3',
  },
  {
    input: "bbbbb",
    result: 1,
    desc: 'value equal to 1',
  },
  {
    input: "pwwkew",
    result: 3,
    desc: 'value equal to 3',
  },
];

for (const [i, testCase] of testCases.entries()) {
  const result = lengthOfLongestSubstring(testCase.input);
  log(`test case ${i} result: `, result === testCase.result ? `✅ passed` : `❌ failed`, result);
  // log(`test case i result: `, result === testCase.result ? `passed ✅` : `failed ❌`, result);
  // log(`test case i =`, testCase);
}


/*
$  npx ts-node ./003\ longest-substring-without-repeating-characters.ts

test case 0 result:  ✅ passed 3
test case 1 result:  ✅ passed 1
test case 2 result:  ✅ passed 3
*/


https://leetcode.com/problems/longest-substring-without-repeating-characters/

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

LeetCode 题解 / LeetCode Solutions

https://www.youtube.com/channel/UCftIXZeipv4MTVwmfFphtYw/videos

YouTube & LeetCode 力扣官方算法题解视频列表

https://www.youtube.com/playlist?list=PLamwFu9yMruCBtS2tHUD77oI_Wsce-syE

https://github.com/xgqfrms/leetcode/issues/14

<iframe allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/fv2skIIXO5w?start=2" title="YouTube video player" width="560"></iframe>

https://www.youtube.com/results?search_query=+Leetcode+3

<iframe allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/watch?v=LupZFfCCbAU?start=32" title="YouTube video player" width="560"></iframe> <iframe allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/watch?v=wiGpQwVHdE0?start=12" title="YouTube video player" width="560"></iframe>

https://neetcode.io/

https://github.com/neetcode-gh/leetcode/blob/main/javascript/3-Longest-Substring-Without-Repeating-Characters.js

https://github.com/neetcode-gh/leetcode/blob/main/typescript/3-Longest-Substring-Without-Repeating-Characters.ts

类似问题

LeetCode

https://leetcode.com/problems//

refs

https://www.cnblogs.com/xgqfrms/p/13649609.html



©xgqfrms 2012-2020

www.cnblogs.com/xgqfrms 发布文章使用:只允许注册用户才可以访问!

原创文章,版权所有©️xgqfrms, 禁止转载

标签:子串,题解,maxStr,maxLen,let,result,https,com,LeetCode
From: https://www.cnblogs.com/xgqfrms/p/16746760.html

相关文章

  • Even Number Addicts - 题解【动态规划/记忆化搜索】
    题面本题是CodeforcesGlobalRound22的C题。原题链接见:C.EvenNumberAddicts。下面搬运一下题面:DescriptionAliceandBobareplayingagameonasequence\(a_......
  • LeetCode160 相交链表
       idea:比较相同信息,首先想到用嵌套for循环解决,方法比较简单,不过时间复杂度高 /** * Definition for singly-linked list. * struct ListNode { *......
  • [Oracle] LeetCode 560 Subarray Sum Equals K 思维+Map
    Givenanarrayofintegersnumsandanintegerk,returnthetotalnumberofsubarrayswhosesumequalstok.Asubarrayisacontiguousnon-emptysequenceof......
  • LeetCode 206 反转链表
    给你单链表的头节点head,请你反转链表,并返回反转后的链表。 示例1:输入:head=[1,2,3,4,5]输出:[5,4,3,2,1]示例2:输入:head=[1,2]输出:[2,1]示例3:输入:head=[]输出......
  • LJT的书库题解
    原题链接题目难度较低,看懂题目后特别好想。注意到题目中说的,一个藏书室最多与两个相同的藏书室相连。那么含有所需书的藏书室是树上的一条链。但是,书的本数未知,且链的两......
  • 【Azure 应用服务】本地Node.js部署上云(Azure App Service for Linux)遇到的三个问题
    问题描述当本地Node.js(Linux+Node.js+npm+yarn)部署上云,选择AzureAppServiceforLinux环境。但是在部署时,遇见了以下三个问题:问题一:使用VSCode进行部署,部署速......
  • leetcode 513. Find Bottom Left Tree Value 找树左下角的值 (简单)
    一、题目大意给定一个二叉树的根节点root,请找出该二叉树的最底层最左边节点的值。假设二叉树中至少有一个节点。示例1:输入:root=[2,1,3]输出:1示例2:......
  • leetcode -- tree 3
    使用归并排序简单解决问题归并排序用传统方法归并classSolution:defsortArray(self,nums:List[int])->List[int]:defmergesort(nums:List[int......
  • 求: 最长回文子串
    给你一个字符串s,找到s中最长的回文子串。 示例1:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。示例2:输入:s="cbbd"输出:"bb" 提示:1<=s.length......
  • CF600C题解
    题意有一串字符串\(S\),设改变\(S\)中的任意一个字符称为1次转变(交换任意2个字符不算转变次数),求在操作最少的情况下可得到的回文字符串正文♦算法:找规律♦准备......