固有の長さの非インドローム部分配列

1930年。固有の長さ 3 の回文サブシーケンス

難易度: 中

トピック: ハッシュ テーブル、文字列、ビット操作、プレフィックス合計

文字列 s を指定すると、s の部分列である長さ 3 の一意の回文の数を返します。

同じサブシーケンスを取得する方法が複数ある場合でも、カウントされるのは 1 回だけであることに注意してください。

回文は、前から見ても後ろから読んでも同じ文字列です。

文字列の

サブシーケンスは、残りの文字の相対的な順序を変更せずに、一部の文字 (なしの場合も可) が削除された元の文字列から生成された新しい文字列です。

たとえば、「ace」は「abcde」の部分列です。

例 1:

• 入力: s = "aabca"
• 出力: 3
• 説明: 長さ 3 の 3 つの回文部分列は次のとおりです。
  「aba」 (「aabca」のサブシーケンス)
  "aaa" ("aabca" の部分列)
  "aca" ("aabca" のサブシーケンス)

例 2:

• 入力: s = "adc"
• 出力: 0
• 説明: 「adc」には長さ 3 の回文部分列がありません。

例 3:

• 入力: s = "bbcbaba"
• 出力: 4
• 説明: 長さ 3 の 4 つの回文部分列は次のとおりです。
  「bbb」 (「bbcbaba」のサブシーケンス)
  「bcb」 (「bbcbaba」のサブシーケンス)
  「bab」 (「bbcbaba」のサブシーケンス)
  「aba」 (「bbcbaba」のサブシーケンス)

制約:

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

ヒント:

長さ 3 の回文文字列の最大数はいくつですか?
特定の位置の左側に表示された文字を追跡するにはどうすればよいですか?

解決策:

接頭辞と接尾辞の文字追跡を活用する効率的なアルゴリズムを使用して、有効な回文部分列をすべてカウントできます。

アプローチ

1. 追跡プレフィックス文字: 配列を使用して、文字列内の各位置の左側にある文字のセットを格納します。これは、文字が回文部分列の最初の部分を形成できるかどうかを効率的にチェックするのに役立ちます。
   

2. 追跡サフィックス文字:
   別の配列を使用して、文字列内の各位置の右側にある文字セットを格納します。これは、文字が回文部分列の 3 番目の部分を形成できるかどうかを効率的にチェックするのに役立ちます。

3. 回文部分列を数える:
   文字列内の各文字を、長さ 3 の回文の中央の文字とみなします。プレフィックス文字とサフィックス文字の有効な組み合わせをすべてチェックして、一意の回文を決定します。

4. ストア結果:
   ハッシュ セットを使用して一意の回文サブシーケンスを保存し、重複がないようにします。

このソリューションを PHP で実装してみましょう: 1930。固有の長さ 3 の回文サブシーケンス

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

// Test cases
echo countPalindromicSubsequence("aabca") . PHP_EOL; // Output: 3
echo countPalindromicSubsequence("adc") . PHP_EOL;   // Output: 0
echo countPalindromicSubsequence("bbcbaba") . PHP_EOL; // Output: 4
?>

説明：

1. プレフィックス配列:

   • 位置 i の各文字について、prefix[i] にはインデックス i より前に出現したすべての個別の文字が格納されます。

2. サフィックス配列:

   • 位置 i の各文字について、suffix[i] にはインデックス i の後に出現するすべての個別の文字が格納されます。

3. 中央の文字:

   • 各文字を回文の中央と考えてください。中央の文字に一致する接頭辞と接尾辞の文字の組み合わせごとに、長さ 3 の回文を形成します。

4. ハッシュマップ:

   • 連想配列 ($uniquePalindrome) を使用して一意の回文を保存し、重複がカウントされないようにします。

複雑

• 時間計算量: O(n)

  • 文字列を 2 回走査して、プレフィックス配列とサフィックス配列を計算します。
  • 3 回目のトラバーサルでは、有効な回文サブシーケンスがチェックされます。

• 空間の複雑さ: O(n)

  • プレフィックス配列とサフィックス配列の場合。

出力

コードは、指定された例に対して正しい結果を生成します。

• 入力: "aabca" → 出力: 3
• 入力: "adc" → 出力: 0
• 入力: "bbcbaba" → 出力: 4

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が固有の長さの非インドローム部分配列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。