運算後字串的最小長度

3223。運算後字串的最小長度

難度：中

主題： 雜湊表、字串、計數

給你一個字串 s。

您可以對任意次執行以下程序：

• 在字串中選擇一個索引i，使得索引i 左側至少有 一個字元等於s[i]，並且至少 一個字元右邊也等於s[i].
刪除索引 i 的
• 左邊 等於 s[i] 的 最接近的 字元。
刪除索引 i 的
• 右邊 等於 s[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次。

解：

我們需要注意字串中每個字元的出現頻率。解決方法如下：

方法：

1. 計算字元頻率:

   使用頻率表來統計每個字元在字串中出現的次數。

2. 減少頻率>= 3的字元:

   如果一個字元出現3次或以上，我們可以重複刪除其中兩個，直到只剩下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]
• 減少後：
  • '一' => 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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是運算後字串的最小長度的詳細內容。更多資訊請關注PHP中文網其他相關文章！