問題

Longest Substring Without Repeating Characters

文字列が与えられるとき、繰り返しを含まない最長文字列数を求める。

例 : ''' Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:

Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring. '''

解答

スライドウィンドウという概念を使用する。

i を開始点、k を終了点として、i 番目から k 番目までの重複が発生しない範囲を求め、k+1 番目の文字が範囲内で重複していなければ、そのまま k+1 を行い、発生していなければ i+1 を行うという概念である。

このイメージはできたんですが、i を 1 つずつ加算するよりスマートなやり方で解答していた例があったのでメモしておく。

解答例には i を増加させる際に、重複が発生した文字 k+1 番目までウィンドウの幅を一気にジャンプさせることで計算量が削減されている。

なお k+1 番目は slide window の開始点 i より手前の可能性があるので、map.get(char) > i の判定は必要。

やっぱりプログラミングを考えるのは楽しい。

やっていき。