部分文字列を削除した後の最小文字列長

2696。部分文字列を削除した後の最小文字列長

難易度: 簡単

トピック: 文字列、スタック、シミュレーション

大文字の英語文字のみで構成される文字列 s が与えられます。

この文字列にいくつかの操作を適用すると、1 回の操作で部分文字列「AB」または「CD」のいずれかを s から削除できます。

取得可能な結果の文字列の最小長さを返します。

文字列は部分文字列を削除した後に連結され、新しい「AB」または「CD」部分文字列が生成される可能性があることに注意してください。

例 1:

• 入力: s = "ABFCACDB"
• 出力: 2
• 説明: 次の操作を実行できます。
  部分文字列「ABFCACDB」を削除し、s = "FCACDB" とします。
  部分文字列「FCACDB」を削除し、s = "FCAB" とします。
  部分文字列「FCAB」を削除し、s = "FC" とします。
  結果の文字列の長さは 2 になります。
  それが取得可能な最小の長さであることが示されます。

例 2:

• 入力: s = "ACBBD"
• 出力: 5
• 説明: 文字列に対して操作を行うことはできないため、長さは変わりません。

制約:

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

ヒント:

問題を解決するために力ずくで解決できますか?
文字列を繰り返し走査し、部分文字列「AB」と「CD」を見つけて削除します。

解決策:

スタックを使用して、部分文字列「AB」と「CD」の削除を処理します。スタックアプローチにより、文字列の走査中にこれらの部分文字列が発生したときにそれらを効率的に削除できます。

アプローチ：

1. スタックを使用する:
   文字列を 1 文字ずつ走査します。
   各キャラクターをスタックにプッシュします。
   スタックの上位 2 文字が部分文字列「AB」または「CD」を形成している場合、これらの 2 文字をスタックからポップします (削除します)。
   入力文字列内のすべての文字に対してこのプロセスを続けます。
2. 最後の文字列:
   走査の終わりに、スタックには縮小された文字列が含まれます。
   可能な最小の長さがスタックのサイズになります。

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

2696。部分文字列を削除した後の最小文字列長

<?php <br>
/**

• @param String $s
• @return Integer /

function minLengthAfterRemovals($s) { ... ... ... /*

• go to ./solution.php */

}

// Example usage:
echo minLengthAfterRemovals("ABFCACDB"); // Output: 2
echo "\n";
echo minLengthAfterRemovals("ACBBD"); // Output: 5
?>

説明:

空のスタック ($stack) を初期化します。
文字列 s の各文字をループします。
スタックの先頭文字を確認します。
• 先頭の文字と現在の文字が部分文字列「AB」または「CD」を形成している場合、array_pop を使用して先頭の文字を削除します。
  それ以外の場合は、現在の文字をスタックにプッシュします。
スタックには、すべての可能な除去後に残ったキャラクターが保持されます。
最後に、count($stack) は結果の文字列の長さを返します。

複雑：

• 時間計算量: O(n)、n は文字列の長さです。各文字は最大 2 回処理されます (1 回プッシュ、1 回ポップ)。
• 空間の複雑さ: 除去が不可能な最悪の場合、スタックは O(n)。

このソリューションは、出現する可能性のある「AB」と「CD」をすべて、見つからなくなるまで削除することで、文字列を効果的に最小化します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で

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

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

• LinkedIn
• GitHub

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