[LeetCode-Medium] Longest Substring Without Repeating Characters

Loading...

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCode

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

題目要求計算最長子字串

使用 sliding window

建立兩個指針left right，一個 set 和一個 counter

其實這題可以使用 array，但使用 set 來降低時間複雜度

使用 while 來 loop 全部的 input string

判斷當前的 string 是否存在在 set 裡面

如果存在，刪除該值並且把 left++

如果不存在，把該值加入 set 中，並比較現在 set size 和 counter 哪者較大

取大者存入 counter

return counter

Solution - javascript

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let counter = 0
    let right = 0
    let left = 0
    let set = new Set()
    while(right < s.length){
        if(set.has(s[right])){
           set.delete(s[left++])
        } else {
            set.add(s[right++])
            counter = Math.max(counter, set.size)
        }
    }
    return counter
};