アルゴリズムの復習：繰り返し文字を含まない最も長い部分文字列

、スライディング・ウィンドウとは何かを示すために、ダブルエンドの待ち行列を使った難しいスライディング・ウィンドウの問題を解きました。このセクションでは、さらに深く分析を続け、スライディングウィンドウ問題のいくつかのパターン化された解法を探ります。

スライディングウィンドウは

スライディングウィンドウタイプのほとんどの問題では、一般的なアイデアは文字列のマッチングを見ることです。より標準的な問題では、パターン文字列Bとターゲット文字列Aが与えられます。次に、Bの修飾ルールを満たすAの部分文字列、またはAの修飾ルールを満たす結果を見つける問題が出題されます。

例えば、文字列sと空でない文字列pが与えられた場合、pの文字のアナグラムであるsの部分文字列をすべて見つけ、それらの部分文字列の開始インデックスを返します。

または：文字列Sと文字列Tが与えられたとき、文字列Sの中にTのすべての文字を含む最小の部分文字列を見つけます。

文字列 s と同じ長さの単語がいくつか与えられたとき、words のすべての単語を連結してできる s の部分文字列の開始位置を求めます。

すべてこのカテゴリに属する標準的な問題です。このカテゴリの一般的な解答は、可変長のスライディングウィンドウを維持することです。ダブルポインタを使おうが、ダブルエンドのキューを使おうが、カーソルのような派手なトリックを使おうが、目的は同じです。

では、具体的な研究テーマを見ていきましょう。

トピックは電子書籍で分析されています。

例1.

 : "abcabcbb"
 : 3 
 : 繰り返しのない最も長い部分文字列は "abc "なので、その長さは3である。

例2.

 : "bbbbb"
 : 1
 : 繰り返し文字を含まない最長の部分文字列は "b "なので、その長さは1である。

例3.

 : "pwwkew"
 : 3
 : 繰り返しのない最も長い部分文字列は "wke "なので、その長さは3である。

pwke "は部分文字列ではなく部分列です。

解答は電子書籍で分析されています。

入力が "abcabcbb "であると仮定すると、直接トピックを分析し、入力文字列で移動するウィンドウを維持するだけです。下図はこれを示しています：

次の要素がウィンドウに表示されない場合、ウィンドウを拡張します。

次の要素がウィンドウに現れると、ウィンドウは縮小し、現れた要素とその左にある要素を削除します：

そのプロセスを通じて、ウィンドウが現れた最大値を記録すれば十分です。そしてやるべきことは、ウィンドウを可能な限り拡大することだけです。

キューでも、ダブルポインタでも、あるいはマップを通しても、それは可能です。

ダブル・ポインター・アプローチの実演

public class Solution {
 public static int lengthOfLongestSubstring(String s) {
 int n = s.length();
 Set<Character> set = new HashSet<>();
 int result = 0, i = 0, j = 0;
 while (i < n && j < n) {
 //charAt: 指定された位置にある文字を返す
 if (!set.contains(s.charAt(j))) {
 set.add(s.charAt(j));
 j++;
 result = Math.max(result, j - i);
 } else {
 set.remove(s.charAt(i));
 i++;
 }
 }
 return result;
 }
}

実施結果：

見てみればわかります。最悪の場合、各文字に左と右の2回アクセスすることになり、時間複雑度はO(2N)となります。わからない人は下の図を見てください：

文字列が "abcdc "だとすると、abcは2回アクセスされます。

では、どうすればさらに最適化できるのでしょうか？

実際には、文字が存在するかどうかを判断するために単にコレクションを調べるのではなく、文字からインデックスへのマッピングを定義することが可能です。そうすることで、重複する文字が見つかった場合、その要素を再訪することなく、ウィンドウを即座にスキップすることができます。

最適化されたコードは以下の通り：

public class Solution {
 public static int lengthOfLongestSubstring(String s) {
 int n = s.length(), result = 0;
 Map<Character, Integer> map = new HashMap<>(); 
 for (int right = 0, left = 0; right < n; right++) {
 if (map.containsKey(s.charAt(right))) {
 left = Math.max(map.get(s.charAt(right)), left);
 }
 result = Math.max(result, right - left + 1);
 map.put(s.charAt(right), right + 1);
 }
 return result;
 }
}

実施結果：

修正後、時間の複雑さは多少改善されたものの、まだ遅いことがわかりました！さらに最適化するには？ハッシュマップの代わりに256ビット配列を使って最適化することができます。

コードのさらなる最適化：

class Solution {
 public int lengthOfLongestSubstring(String s) {
 int n = s.length();
 int result = 0;
 int[] charIndex = new int;
 for (int left = 0, right = 0; right < n; right++) {
 char c = s.charAt(right);
 left = Math.max(charIndex[c], left);
 result = Math.max(result, right - left + 1);
 charIndex[c] = right + 1;
 }
 return result;
 }
}

実施結果：

最適化後、時間の複雑さが大幅に改善されることがわかりました！ここで簡単に理由を説明すると、配列とハッシュマップへのアクセスでは、誰が速く、誰が遅いかは確実ではなく、ハッシュマップの基本的な実装やデータのサイズについて考える必要があります。しかし、ここで、アクセスするデータの既知の添え字は、直接対処することができますので、大幅にクエリ時間を短縮します。

要約

この問題は基本的にこれで終わりです。最後に一言、一般的に、問題を分析するのであれば、圧縮して圧縮してまた圧縮して、繭のように最後まで行き、できるだけ最適な形で問題を完成させることをお勧めします。自分で最適解を考える必要はありませんが、単に問題を完成させるということだけは絶対にしないでください！

私が書いたすべての解答と各問題の完全な図解をeBookにまとめました。