BETA

3. Longest Substring Without Repeating Characters (Medium)

投稿日:2019-03-02
最終更新:2019-03-02

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 とかを加えて検索すると情報が出てくる。

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

https://leetcode.com/ の Problems の解法を載せています。ネタバレ注意。

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる
技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
or 外部アカウントではじめる
10秒で技術ブログが作れます!