[LeetCode] 3. Longest Substring Without Repeating Characters

23085 ワード
アルゴリズム#アルゴリズム# leetcode テキストリンク

3. Longest Substring Without Repeating Characters


質問リンク:https://leetcode.com/problems/longest-substring-without-repeating-characters/

指定した文字列に重複しない最大長文字列の問題を返します.

Solution


1. Bruteforce


Breutforceメソッドから、指定した文字列で作成できるすべてのサブストリングにRepeating Charactersがあるかどうかを確認する必要があります.

Algorithm


  • すべてのsubstringを調べるために、2つのfor loopを使用して、外部ループのiは0からn-1(nは文字列の長さ)、内部ループのjはi+1からnまで巡回する.
    このとき、作成可能なすべての文字列をチェックするには、長さが1の文字列も含まなければならないので、jはi+1から始まるかiから始まるかを考慮しなければならない.
    testcaseがbbbbbである場合、重複文字のない最長substringの長さは1であるため、jはiからループを開始する.

  • 作成したsubstringについて、重複文字があるかどうかを確認します.
    文字の繰り返しチェックにはHashSetが使用できます.
    →重複する文字が存在しない場合は、maxLengthを更新します.

    • インプリメンテーション

    class Solution {
    public int lengthOfLongestSubstring(String s) { 
        if(s.length() <= 1) return s.length();
        
        int maxLength=0;
        for(int i=0; i<s.length()-1; i++) {
            for(int j=i; j<s.length(); j++) {
                if(allUnique(s, i, j)) maxLength = Math.max(maxLength, j-i+1);
            }
        }
        return maxLength;
    }
    
    boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        
        for(int i=start; i<=end; i++) {
            if(set.contains(s.charAt(i))) return false;
            set.add(s.charAt(i));
        }
        return true;
    }
}
    結果はTLEであり,O(n^3)の時間的複雑度で作成できるすべての文字列を調べているからである.

    1-1. Bruteforce Optimized


    以前の解答では,作成可能なすべての文字列を調べ,すべての文字列に対してHashSetを作成し,文字列の先頭から末尾までを調べた.この部分は最適化できる.

    Algorithm


    生成可能なすべての文字列をチェック

  • →重複が発生した場合は重複が発生した文字列であるためbreak j loop
  • のすべての文字列に対してHashSetを生成し、文字列を最初から最後までチェックします.
    →重複文字がチェックされていない文字列については、再度重複を実行する必要はありません.
    次の文字列をチェックするときにSetに入れる文字を初期化しないように、Setをグローバル管理します.

    • インプリメンテーション

    class Solution {
    Set<Character> set = new HashSet<>();
    public int lengthOfLongestSubstring(String s) { 
        if(s.length() <= 1) return s.length();
        
        int maxLength=0;
        for(int i=0; i<s.length()-1; i++) {
            set.add(s.charAt(i));
            for(int j=i; j<s.length(); j++) {
                if(j!=i && set.contains(s.charAt(j))) break;
                maxLength = Math.max(maxLength, j-i+1);
                set.add(s.charAt(j));
            }
            set.clear();
        }
        return maxLength;
    }
}

    2. Sliding Window


    インプリメンテーション

    class Solution {
    public int lengthOfLongestSubstring(String s) { 
        if(s.length() <= 1) return s.length();
        Set<Character> set = new HashSet<>();
        
        int i=0; 
        int j=0;
        int maxLength=0;
        while(i<s.length() && j<s.length()) {
            if(!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                maxLength = Math.max(maxLength, j-i);
            }
            else set.remove(s.charAt(i++));
        }
        return maxLength;
    }
}

    2-1. Sliding Window Optimized


    インプリメンテーション

    class Solution {
	public int lengthOfLongestSubstring(String s) {
              int maxLength = 0;
              Map<Character, Integer> map = new HashMap<>();
              int slow = 0;
              int fast = 0;
              while(fast < s.length()) {
                  char c = s.charAt(fast);
                  if(map.containsKey(c)) {
                          slow = Math.max(map.get(c)+1, slow);
                  }
                  map.put(c, fast);
                  fast++;
                  maxLength = Math.max(maxLength, fast-slow);
              }
              return maxLength;
        }
}
    文字列のindexをHashMapで保存すると、whileを繰り返し文字に変換することなく、slowに直接変換できます.
    注意!HashMapに格納されているインデックス値は、現在のslowインデックスの前に、Math.maxに移動してください.
    [Zaranara]スライダ回転機能を実現
    前コース1週間