繰り返しのない最長文字列数を求める

問題

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 の判定は必要。

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

やっていき。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする