文字を繰り返さずに最長の部分文字列を検索する

投稿日: 2019-10-19 2022-10-27
タグ: Java, Java String

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. 最適化されたアプローチ

それでは、最適化されたアプローチを見てみましょう。文字列を左から右にトラバースし始め、以下を追跡します。

startおよびendインデックスを使用した非反復文字を含む現在のサブストリング
最長の非反復部分文字列出力
すでに訪問した文字のルックアップテーブル

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;
}

新しいキャラクターごとに、すでに訪れたキャラクターでそれを探します。文字がすでにアクセスされており、繰り返されない文字を含む現在のサブ文字列の一部である場合は、開始インデックスを更新します。それ以外の場合は、文字列のトラバースを続行します。

文字列を1回だけトラバースするため、時間計算量は線形、つまりO（n）になります。

このアプローチは、スライディングウィンドウパターンとも呼ばれます。

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. 結論

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

そして、いつものように、ソースコードはGitHubで利用できます。

getdocs

13036