3. Longest Substring Without Repeating Characters (Medium)

https://leetcode.com/problems/longest-substring-without-repeating-characters/

与えられた文字列から、重複する文字を含まない最長の部分文字列の長さを求めよという問題。
最初はBrute Forceで解こうとして、時間かかりすぎって怒られた。

回答

# @param {String} s  
# @return {Integer}  
def length_of_longest_substring(s)  
    h = {}  
    n = s.length  
    max, i, j = 0, 0, 0  
    while (i < n && j < n)  
        unless h[s[j]]  
            h[s[j]] = 1  
            j += 1  
            max = h.length if max < h.length  
        else  
            h.delete(s[i])  
            i += 1  
        end  
    end  

    max  
end

ユニークな文字列を探すために、左端を固定して右に順番に伸ばしていき、重複する文字が見つかったらハッシュに格納してある左端の文字を削除しながら進むというやり方。Sliding Window と呼ばれるテクニックのようだ。
Sliding Windowだけで検索すると通信プロトコルの作法ばかりが出てくるので、String とか Array とかを加えて検索すると情報が出てくる。