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

難易度: 中

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

英小文字で構(gòu)成される文字列 s が與えられます。

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

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

部分文字列は、文字列內(nèi)の連続した空ではない文字シーケンスです。

例 1:

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

例 2:

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

例 3:

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

制約:

3 s は英小文字のみで構(gòu)成されます。

ヒント:

制約は小さいです。
すべての部分文字列を総當(dāng)たりでチェックします。

解決策:

s には小さな制約があるため (長さは最大 50)、総當(dāng)たりアプローチを使用できます。私たちは次のようにします:

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

このソリューションを PHP で実裝してみましょう:

2981。 3 回出現(xiàn)する最長の特殊部分文字列を検索 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. 外側(cè)ループ: 可能な長さの部分文字列を最長のものから順に繰り返します。これにより、最長の特殊部分文字列が見つかったらすぐにそれを返すことが保証されます。
2. スライディング ウィンドウ: 部分文字列の長さごとに、スライディング ウィンドウのアプローチを使用して、その長さのすべての部分文字列を抽出します。
3. 部分文字列のカウント: 連想配列 ($countMap) を使用して、各部分文字列の出現(xiàn)を保存およびカウントします。
4. 特別なチェック: ヘルパー関數(shù) isSpecial は、部分文字列が 1 つの繰り返し文字のみで構(gòu)成されているかどうかをチェックします。
5. 結(jié)果を返す: 有効な部分文字列が見つかった場(chǎng)合は、その長さを返します。それ以外の場(chǎng)合は、-1 を返します。

複雑

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

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

連絡(luò)先リンク

このシリーズが役立つと思われた場(chǎng)合は、GitHub で リポジトリ にスターを付けるか、お?dú)荬巳毪辘违僵`シャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場(chǎng)合は、お?dú)葺Xにフォローしてください:

• LinkedIn
• GitHub

以上が3 回出現(xiàn)する最長の特殊部分文字列の検索 Iの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。