]

1.概要

このチュートリアルでは、Javaを使用して固有の文字の最長の部分文字列を見つける方法を比較します。たとえば、「CODINGISAWESOME」の一意の文字の最長の部分文字列は「NGISAWE」です。

2.ブルートフォースアプローチ

素朴なアプローチから始めましょう。まず、** 各サブストリングに一意の文字が含まれているかどうかを調べます。 

String getUniqueCharacterSubstringBruteForce(String input) {
    String output = "";
    for (int start = 0; start < input.length(); start++) {
        Set<Character> visited = new HashSet<>();
        int end = start;
        for (; end < input.length(); end++) {
            char currChar = input.charAt(end);
            if (visited.contains(currChar)) {
                break;
            } else {
                visited.add(currChar);
            }
        }
        if (output.length() < end - start + 1) {
            output = input.substring(start, end);
        }
    }
    return output;
}


n

（n 1）/2


個の可能な部分文字列があるので、 このアプローチの時間の複雑さは

O（n ^ 2）

です。

3.最適化されたアプローチ

それでは、最適化されたアプローチを見てみましょう。文字列を左から右へたどり始め、次のことを追跡します。

  1. の助けを借りて、繰り返しのない文字を含む現在の部分文字列


start

と

end

のインデックス
。最長の非繰り返しサブストリング

output


  1. すでに

    visited

    文字のルックアップテーブル
     

String getUniqueCharacterSubstring(String input) {
    Map<Character, Integer> visited = new HashMap<>();
    String output = "";
    for (int start = 0, end = 0; end < input.length(); end++) {
        char currChar = input.charAt(end);
        if (visited.containsKey(currChar)) {
            start = Math.max(visited.get(currChar)+1, start);
        }
        if (output.length() < end - start + 1) {
            output = input.substring(start, end + 1);
        }
        visited.put(currChar, end);
    }
    return output;
}

すべての新しいキャラクターについて、私たちはすでに訪れたキャラクターの中でそれを探します。その文字がすでに訪問されていて、繰り返していない文字を含む現在の部分文字列の一部である場合は、開始インデックスを更新します。それ以外の場合は、引き続き文字列を移動します。

文字列を一度だけ横断しているので、

時間の複雑さは線形になります、または

O（n）

。

  • このアプローチはhttps://medium.com/leetcode-patterns/leetcode-pattern-2-sliding-windows-for-strings-e19af105316b[スライドウィンドウパターン]としても知られています。**

4.テスト

最後に、それが機能することを確認するために我々の実装を徹底的にテストしましょう: 

@Test
void givenString__whenGetUniqueCharacterSubstringCalled__thenResultFoundAsExpected() {
    assertEquals("", getUniqueCharacterSubstring(""));
    assertEquals("A", getUniqueCharacterSubstring("A"));
    assertEquals("ABCDEF", getUniqueCharacterSubstring("AABCDEF"));
    assertEquals("ABCDEF", getUniqueCharacterSubstring("ABCDEFF"));
    assertEquals("NGISAWE", getUniqueCharacterSubstring("CODINGISAWESOME"));
    assertEquals("be coding", getUniqueCharacterSubstring("always be coding"));
}

ここでは、境界条件とより一般的なユースケース

を試して

テストします。

5.まとめ

このチュートリアルでは、スライディングウィンドウ手法を使用して、繰り返しのない文字を含む最も長い部分文字列を見つける方法を学びました。

そして、いつものように、ソースコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-1[over on GitHub]から入手できます。

]