Leetcode #3. Longest Substring Without Repeating Characters プログラミング練習

java leetcode medium プログラミング練習

問題：

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", 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.

難易度:　medium
入力:　String
目的: 入力された文字列の中で一番長い重複なしの文字列の長さを探せ
出力:　int
注意:　目標文字列はsubstringである事。（pwwkewの答えはwkeでありpwkeではない）

文字列の処理問題です。
初心者がよく一番最初に思いつくのがforで回してi番目の文字から始まる一番長い重複なしのstringの長さなのですが、
処理時間がO(n*n)になってしまい、Time Limit Exceededになってしまいます。
Leetcodeの問題は基本n*nで解けるものですがAcceptされた記憶がないのでまず他の方法を考えましょう。
面接の際も同じです。n*nの答えを出せば直ぐに面接官から”もっと早い書き方ないかな？”と聞かれます。
そうすると時間が大体は足りなくなってしまうので出来るだけ避けましょう。
わからなくても考え込むと大体ヒントをくれますよー

今回私はSliding Windowで解きました。
こういった問題ではよく使われる方法なので知らない人は覚えておきましょう！

以下、自分の回答です。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        HashSet set = new HashSet();
        int left = 0;
        int right = 0;
        int result = 0;
        while (right < len) {
            if(!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
                result = Math.max(result, set.size());
            }
            else {
                set.remove(s.charAt(left));
                left++;
            }
        }
        return result;
    }
}

例題で説明しますと
まずleft, rightをポインタとして用意しておきます。
重複を探す為のHashSetを用意。

p　w　w　k　e　w　　　　
↑

left とrightが同じ位置にあるので重複なし。pをHashSetに格納

p　w　w　k　w
↑ ↑　　　　　　

重複がないのでright++,　wをHashSetに格納

p　w　w　k　e　w
↑　　↑　　　　　　

wが既にHashSetの中にあるのでleftが指すpをSetから取り除き, left++

p　w　w　k　e　w
　↑　↑

wが既にHashSetの中にあるのでleftが指すwをSetから取り除き, left++

p　w　w　k　e　w
　　　↑

又leftとrightが重なりましたね。HashSetの中身は空なのでwを格納しright++

p　w　w　k　e　w
　　　↑　 ↑

重複がないのでright++,　rightが指すkをHashSetに格納

p　w　w　k　e　w
　　　↑　　↑

重複がないのでright++,　rightが指すeをHashSetに格納

p　w　w　k　e　w
　　　↑　 　　　↑

wが既にHashSetの中にあるのでleftが指すwをSetから取り除き, left++

p　w　w　k　e　w
　　　　　↑　　↑

重複がないのでright++,　rightが指すwをHashSetに格納

rightが文字列の長さを超えたのでbreak。後は処理中に一番長かったsubstringの長さを出力すればいいだけです。
Time complexityはO(n)です。
ふと思うと長さを求めればいいのでwindowの長さを維持しつつ重複があればright++なければleftとright共に++,していけばいいのかも...？
まあどのみちO(n)はかかるのでいっか（笑）

ではでは