演算後の文字列の最小長-PHPチュートリアル-php.cn

演算後の文字列の最小長

DDD

リリース： 2025-01-13 22:30:46

オリジナル

244 人が閲覧しました

Minimum Length of String After Operations

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 は英小文字のみで構成されます。

ヒント:

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

解決策:

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

アプローチ：

文字の頻度を数える:
- 頻度表を使用して、文字列内に各文字が出現する回数を数えます。
頻度 >= 3 で文字を削減します:
- キャラクターが 3 回以上出現する場合は、2 つの出現のみが残るまで、そのうちの 2 つを繰り返し削除できます。
最小長を計算します:
- 頻度を減らした後のすべての文字の残りのカウントを合計します。

このソリューションを 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";
?>

ログイン後にコピー

説明：

頻度カウント:
- 文字列を反復処理し、文字ごとに $frequency 配列内のカウントをインクリメントします。
文字の削減:
- $frequency 配列内の各文字について、その数が 3 以上であるかどうかを確認します。その場合は、最大 2 まで減らします。
結果の計算:
- $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。

複雑：

時間計算量:
- 頻度のカウント: O(n)、n は文字列の長さです。
- リダクション: O(1) (小文字は 26 個しかないため定数時間)。
- 加算周波数: O(1).
- 全体: O(n).
空間の複雑さ:
- O(1)。周波数配列には最大 26 個のエントリがあるためです。