アルゴリズム1000本ノック（９）: Longest Substring Without Repeating Characters

問題

本問は LeetCode から引用しております.

与えられた文字列から, 同じ文字を含まない最長の部分文字列の長さを返却せよ.
たとえば "abcabcbb" であれば "abc" の長さ3, "bbbbb" であれば "b" の長さ1となる.

解法

与えられた文字列を1度走査するだけで解くことができます. 各文字について, 既に文字列中に存在していたかどうかを把握するために HashMapにインデックスを値として格納していきます.

上図の例のように, 重複する文字を見つけるまではひたすら長さを伸ばしていき, あるインデックス j で重複を検出( その文字列は既にインデックス i に存在していた ) したら, その時点での最長の文字列は S[i+1] 〜 S[j] になる事がわかります. それ以降の走査においてはインデックス i+1 以降のみを対象に同じ処理を繰り返していきます. つまりここから先では i+1 を開始点としてそれ以前に文字が存在していたかどうかは気にしなくてよくなる, ということです.

Java code:

計算量: O(N), space 空間量: O(N) (Nは与えられた文字列長).