森田賢二のleetCodeの使い方、解説、解答を毎日更新しているキャラクター

[leetcode]問題解答と解説。3. Longest Substring Without Repeating Characters [JavaScript]

[leetcode]問題解答と解説。3. Longest Substring Without Repeating Characters [JavaScript]

皆さんleetCode好きですよね。私も好きです。
なかなかやる機会がないのですよね。
leetCodeの使い方や解説ではなく実際に問題を解決するために何をしたか
をメモ書きして行きます

私はある決意をして今挑んでいます。
モチベーションを保つためだけにこれをやっています。

では今日のleetCode。
【3. Longest Substring Without Repeating Characters】の解決策と方法。自分がまず挑戦して
やったことをさらけ出します。

※下にある自分のコードは自分で設けた制限時間内に書けたところまです。

これは
「私は年末までこれを続けたらどんなleetCoderになるか」のシリーズ。
実験的ブログ更新です。

森田賢二のleetCode
森田賢二のleetCode

[leetcode] 3. Longest Substring Without Repeating Characters ルール

exampleは実際の問題ページを見てください

[leetcode] 3. Longest Substring Without Repeating Characters 問題ページ

3. Longest Substring Without Repeating Characters

[leetcode] 3. Longest Substring Without Repeating Characters

my code is not good

 if(s.length === 0) return 0
    let longestNum = 0
    let count = 0
    let map = {}
    for (let ss of s) {
        if(map[ss] <= 2){
            map = {}
            count = 0
            continue;
        }
        map[ss] = (map[ss] || 0) + 1
        count++
        longestNum = longestNum < count ? count : longestNum
    }
    return longestNum

撃沈

[leetcode] 3. Longest Substring Without Repeating Characters。discussの中の一つの解答例

数ある中からJavaScriptのもので、理解しやすい解説をピックアップしました。
discussから見ればさらにもっと違う方法で真似したくなるものがあるかもしれないですね

JavaScriptでfilterされている、discussはこちらから

3. Longest Substring Without Repeating Characters

function lengthOfLongestSubstring(s: string): number {
  if(s.length === 0) return 0
    let set = new Set()
    let right = 0, left = 0, longest = 0;
    while(right < s.length){
        if(!set.has(s.charAt(right))){
            set.add(s.charAt(right))
            longest = Math.max(set.size , longest)
            right++
        } else {
            set.delete(s.charAt(left))
            left++
        }
    }
    return longest
}

solution 2

https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/731639/JavaScript-Clean-Heavily-Commented-Solution

function lengthOfLongestSubstring(s: string): number {
  let maxLength = 0, start = 0, map = new Map(); // 追跡:current最大値、current始まり位置, indexByChar辞書
    for(let i = 0; i < s.length; i++){
        if(map.has(s[i])) start = Math.max(map.get(s[i]) + 1, start) // 既出ならインデックスに1を足して出現位置をスタートに代入
        map.set(s[i], i) // 辞書の更新
        maxLength = Math.max(i - start + 1, maxLength) // 最大値の更新
    }
    return maxLength
};

[leetcode] 3. Longest Substring Without Repeating Charactersをやってみて感想

書き方として

  • O(n)でできるのですね

カテゴリー leetCode