LeetCode 3. Longest Substring Without Repeating を完全に理解する by TypeScript

Longest Substring Without Repeating Characters

問題文

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

日本語 by DeepL

文字列 s が与えられたとき、文字の繰り返しのない最長の部分文字列の長さを求めよ。

例題

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

検討

重複するまでカウントを増やしていって、重複したらカウントを0にするみたいな感じかなぁ……という方針。
a: 0
b: 0
c: 0
length:0
maxLength: 0
みたいなオブジェクトをループしながらつくって
1の間は良くて2ができたらlength0に戻して……みたいなことを考えたが
計算量的に駄目っぽいので回答をいただいてきました。
どこから解法を借りてきたのか忘れた……。

回答

function lengthOfLongestSubstring(s: string): number {
  /* 現在のループのstringを入れる */
  let currentString: string[] = [];

  /* 最長の文字の長さをカウントしていく */
  let longest = 0;

  /* 文字の長さだけループを行う */
  for (let i = 0; i < s.length; i++) {
    /*
      currentStringにs[i]が含まれているかどうかをチェックしている
      s[i]というのは、今回の文字である。
      例えば、abcabcbbという文字列があったとき
      1回目のループではaが入っている。
      2回めのループではbが入っている。
      posは、currentStringにs[i]が含まれている場合のindexを返す。
      どういうことかというと
      ループの最後のほうで、今回の文字をcurrentStringという文字の配列に入れる。
      ここで重複があるかどうかを判断している、ということ。
      array.indexOfは重複がなければ-1, あればindexが返ってくる。
      だからabcabcbbの場合、abcまでは-1が返ってくる。
      次のaのときにindex3が返ってくる。
    */
    const pos = currentString.indexOf(s[i]);

    /*
      pos !== -1ということは
      indexOfで-1が返って来なかったときなので
      重複があったときのことを指す。
      重複があったときにarray.spliceを使う。
      spliceとは
      https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/splice
      これを使うと、配列の中身を削除したり、追加したりできる。
      splice(start, deleteCount, item1...)
      startは、削除を開始するindex
      deleteCountは、削除する数
      item1...は、追加する要素
      例えば、[a, b, c]という配列があったとする。
      今回は重複していたので、splice(0, pos + 1)を行う。
      これは、0番目からpos + 1番目までを削除するということ。
      posとは、重複している文字のindexである。
      abc[a]のここでposが3になる。から
      0番目から3番目までを削除するということ。

      べつにspliceとか使わなくても[]で空にすればいいんじゃねって思うけど
      たとえばdvdfという文字列が与えられたとき
      dvdのここで全部消しちゃうと、最後のdfだけになってしまう。
      だからdだけ消して、vdfの長さ3が正解。
      splice(0, pos + 1)であれば、dだけ消えます。ちゃんと。
    */
    if (pos !== -1) currentString = currentString.splice(0, pos + 1);

    /* 文字列リストに文字を足す */
    currentString = [...currentString, s[i]];

    /* 
      回答となる最長の文字数を更新する。
      Math.maxは
      https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Math/max
      Math.max([value1[, value2[, ...]]])で、与えられたvalueの最大値を返す。
      今回は使わないけれど、もし配列のなかの最大の数がほしいときは
      Math.max(...ary); というようにスプレッド構文でできる。
      でもこれは正確ではなくて、正確にやりたいならreduceのほうが良いらしいが……
      簡易的に配列の最大値がほしいときにたまに使う。
      でも自分で実装するよりもlodashとかramdaとか使ったほうが良くないか説もある。
    */
    longest = Math.max(longest, currentString.length);
  }

  /* 最長の文字数が答えだ */
  return longest;
}

考え方がわかれば非常にシンプル。
最初に答えを見たときはspliceのところが少しわからなかった。
配列全部空にすればいいじゃんと思ったけど、そうではない。
そういえばleetcodeはlodashが使えるんだけど、実際のコーディング面接でライブラリが使えるかどうかわからないので、個人的には使わずに解いたほうが良いのかなぁ、と思う。
簡単なrange関数とかは自力で実装できたほうが良さそう。
([...Array(5).keys()])

1. currentStringを定義する。
2. 最長の文字の長さをカウントする変数をつくる。
3. ループを回す。
4. currentStringにすでに含まれているかどうかを確認する
5. indexOfで-1以外のときは、含まれている部分を消す。
6. currentStringに今回のループの文字を足す
7. 最長の文字列を更新する