3 回出現する最長の特殊部分文字列の検索 I

2981年。 3 回出現する最長の特殊部分文字列を検索 I

難易度: 中

トピック: ハッシュ テーブル、文字列、二分探索、スライディング ウィンドウ、カウント

英小文字で構成される文字列 s が与えられます。

文字列が 1 文字だけで構成されている場合、その文字列は 特殊 と呼ばれます。たとえば、文字列「abc」は特別ではありませんが、文字列「ddd」、「zz」、および「f」は特別です。

少なくとも 3 回出現する s の 最長の特殊部分文字列の長さを返します。、または特殊な部分文字列が少なくとも 3 回出現しない場合は -1を返します。

部分文字列は、文字列内の連続した空ではない文字シーケンスです。

例 1:

• 入力: s = "aaaa"
• 出力: 2
• 説明: 3 回出現する最長の特殊部分文字列は「aa」です。部分文字列「aaaa」、「aaaa」、および「aaaa」です。
  達成可能な最大長は 2 であることがわかります。

例 2:

• 入力: s = "abcdef"
• 出力: -1
• 説明: 少なくとも 3 回出現する特別な部分文字列は存在しません。したがって、-1 を返します。

例 3:

• 入力: s = "abcdef"
• 出力: 1
• 説明: 3 回出現する最長の特殊部分文字列は「a」です。部分文字列「abcaba」、「abcaba」、および「abcaba」です。
  達成可能な最大長は 1 であることがわかります。

制約:

3 s は英小文字のみで構成されます。

ヒント:

制約は小さいです。
すべての部分文字列を総当たりでチェックします。

解決策:

可能な長さの部分文字列を (最長から最短まで) 繰り返します。
指定された長さのすべての部分文字列をチェックし、その出現数をカウントします。
部分文字列が少なくとも 3 回出現する場合、それが特別なもの (1 つの繰り返し文字で構成されている) かどうかを確認します。
そのような最長の部分文字列の長さを返します。条件を満たす部分文字列がない場合は、-1 を返します。

2981。 3 回出現する最長の特殊部分文字列を検索 I

<?php
/**
 * @param String $s
 * @return Integer
 */
function maximumLength($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if a substring is special
 *
 * @param $substring
 * @return bool
 */
function isSpecial($substring) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maximumLength("aaaa") . "\n"; // Output: 2
echo maximumLength("abcdef") . "\n"; // Output: -1
echo maximumLength("abcabcabc") . "\n"; // Output: 1
?>

説明：

1. 外側ループ: 可能な長さの部分文字列を最長のものから順に繰り返します。これにより、最長の特殊部分文字列が見つかったらすぐにそれを返すことが保証されます。
2. スライディング ウィンドウ: 部分文字列の長さごとに、スライディング ウィンドウのアプローチを使用して、その長さのすべての部分文字列を抽出します。
3. 部分文字列のカウント: 連想配列 ($countMap) を使用して、各部分文字列の出現を保存およびカウントします。
4. 特別なチェック: ヘルパー関数 isSpecial は、部分文字列が 1 つの繰り返し文字のみで構成されているかどうかをチェックします。
5. 結果を返す: 有効な部分文字列が見つかった場合は、その長さを返します。それ以外の場合は、-1 を返します。

複雑

• 時間計算量: 最悪の場合、O(n³)。
  1. n 個の部分文字列長を繰り返します。
  2. 長さごとに O(n) 個の部分文字列を抽出します。
  3. 各部分文字列が特殊かどうかを確認します。これには O(n) 時間がかかります。
• 空間複雑度: 部分文字列カウント マップによる O(n²)。

この強引なアプローチは、制約 (n ) を考慮すると実現可能です。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が3 回出現する最長の特殊部分文字列の検索 Iの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。