演算後の文字列の最小長

3223。操作後の文字列の最小長

難易度: 中

トピック: ハッシュ テーブル、文字列、カウント

文字列 s が与えられます。

次のプロセスは何度でも実行できます:

• インデックス i の左側に s[i] に等しい少なくとも 1 文字が 少なくとも 存在し、かつ 少なくとも 1 文字が存在するように、文字列内のインデックス i を選択します。右側も s[i] に等しいです。
• インデックス i の 左にある、s[i] に等しい 最も近い 文字を削除します。
• s[i] に等しい、インデックス i の右にある最も近い文字を削除します。

達成可能な最終文字列 s の最小長を返します。

例 1:

• 入力: s = "abaacbcbb"
• 出力: 5
• 説明: 次の操作を実行します。
  • インデックス 2 を選択し、インデックス 0 と 3 の文字を削除します。結果の文字列は s = "bacbcbb" です。
  • インデックス 3 を選択し、インデックス 0 と 5 の文字を削除します。結果の文字列は s = "acbcb" です。

例 2:

• 入力: s = "aa"
• 出力: 2
• 説明: 操作は実行できないため、元の文字列の長さを返します。

制約:

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

ヒント:

1. 最終的な答えを見つけるには、各文字の頻度のみが重要です。
2. 文字の出現回数が 3 回未満の場合、その文字を使用した処理は実行できません。
3. 文字列内に少なくとも 3 回出現する文字があると仮定すると、最大 2 回出現するまでこれらの文字のうち 2 つを繰り返し削除できます。

解決策:

文字列内の各文字の頻度に注目する必要があります。それを解決するアプローチは次のとおりです:

アプローチ：

1. 文字の頻度を数える:

   • 頻度表を使用して、文字列内に各文字が出現する回数を数えます。

2. 頻度 >= 3 で文字を削減します:

   • キャラクターが 3 回以上出現する場合は、2 つの出現のみが残るまで、そのうちの 2 つを繰り返し削除できます。

3. 最小長を計算します:

   • 頻度を減らした後のすべての文字の残りのカウントを合計します。

このソリューションを PHP で実装してみましょう: 3223。操作後の文字列の最小長

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

// Example 1
$s1 = "abaacbcbb";
echo "Input: $s1\n";
echo "Output: " . minimumLength($s1) . "\n";

// Example 2
$s2 = "aa";
echo "Input: $s2\n";
echo "Output: " . minimumLength($s2) . "\n";
?>

説明：

1. 頻度カウント:

   • 文字列を反復処理し、文字ごとに $frequency 配列内のカウントをインクリメントします。

2. 文字の削減:

   • $frequency 配列内の各文字について、その数が 3 以上であるかどうかを確認します。その場合は、最大 2 まで減らします。

3. 結果の計算:

   • $frequency 配列の値を合計して、文字列の最小長を取得します。

チュートリアルの例:

例 1:

• 入力: s = "abaacbcbb"
• 頻度: ['a' => 3、'b' => 4、'c' => 2]
• 削減後:
  • 'a' => 2 (3 から削減)、
  • 'b' => 2 (4 から削減)、
  • 'c' => 2 (削減の必要はありません)。
• 最小長: 2 2 2 = 6。

例 2:

• 入力: s = "aa"
• 頻度: ['a' => 2]
• 頻度が 3 以上のキャラクターはいないため、減らす必要はありません。
• 最小長: 2。

複雑：

1. 時間計算量:

   • 頻度のカウント: O(n)、n は文字列の長さです。
   • リダクション: O(1) (小文字は 26 個しかないため定数時間)。
   • 加算周波数: O(1).
   • 全体: O(n).

2. 空間の複雑さ:

   • O(1)。周波数配列には最大 26 個のエントリがあるためです。

この解決策は効率的であり、問​​題の制約内でうまく機能します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が演算後の文字列の最小長の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。