從左、右各取K個字符

2516。從左右各取K個字元

難度：中

主題：雜湊表、字串、滑動視窗

給定一個由字元 'a'、'b' 和 'c' 組成的字串 s 以及一個非負整數 k。每分鐘，您可以選取 s 的最左邊字符，或 s 的最右邊字符。

傳回最少取得至少 k 個字元所需的分鐘數，如果不可能取得每個字元的k 個，則傳回-1角色 。

範例1：

• 輸入： s = "aabaaaacaabc", k = 2
• 輸出： 8
• 解釋：從 s 左邊取三個字元。您現在有兩個“a”字元和一個“b”字元。
  • 從 s 右側取五個字元。您現在有四個“a”字元、兩個“b”字元和兩個“c”字元。
  • 總共需要3 5 = 8分鐘。
  • 可以證明8是最少需要的分鐘數。

範例2：

• 輸入： s = "a", k = 1
• 輸出： -1
• 解釋： 不可能取 'b' 或 'c'，因此回傳 -1。

約束：

• 1 5
• s 僅由字母 'a'、'b' 和 'c' 組成。
• 0

提示：

1. 先計算每個字元的出現頻率並檢查是否可能。
2. 如果從左側取x個字符，那麼從右側最少需要取多少個字符？對 0 ≤ x ≤ s.length 範圍內的所有 x 值求此值。
3. 使用兩指標方法來避免多次計算相同的資訊。

解：

我們可以使用帶有兩個指標的滑動視窗技術來找到從左側和右側取出至少 k 個字元（'a'，'b'，'c'）所需的最小分鐘數字串。

問題分解：

• 給定一個只包含 'a'、'b' 和 'c' 的字串 s。
• 我們需要從字串的最左邊或最右邊的字元中取得每個字元至少出現的 k 次。
• 我們需要確定實現此目標所需的最小分鐘數，如果不可能，則傳回 -1。

方法：

1. 初步檢查：

   • 如果 k == 0，我們可以直接回傳 0，因為不需要任何字元。
   • 如果 k 超過字串中任意字元出現的次數，則立即傳回 -1。

2. 頻率計數:

   • 我們需要統計 'a'、'b' 和 'c' 在字串 s 中出現了多少次，以確保甚至可以收集到每個字元的 k 個。

3. 滑動視窗技術:

   • 使用兩個指標（左和右）的滑動視窗方法。
   • 維護兩個指針，並從字串兩端滑動它們以收集所需的字元。
   • 對於從左側取出的每個字符，計算需要從右側取出的最少字符數才能滿足要求。

4. 最佳化：

   • 我們可以在擴展或收縮視窗時追蹤字元計數，而不是重複地重新計算每個視窗的字元計數。

讓我們用 PHP 實作這個解：2516。從左右各取K個

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

// Example 1
echo takeCharacters("aabaaaacaabc", 2);  // Output: 8

// Example 2
echo takeCharacters("a", 1);  // Output: -1
?>

解釋：

1. 初始設定：

   • 我們計算整個字串中「a」、「b」和「c」的出現次數，以確保可以收集至少 k 個字元。
   • 如果任意字元數小於 k，則傳回 -1。

2. 滑動視窗:

   • 我們使用兩個指標（左和右）從兩端建立一個滑動視窗。
   • 我們透過移動右側指標來擴展視窗並增加遇到的字元數。
   • 一旦目前視窗中的每個字元至少有 k 個，我們就會嘗試從左側縮小視窗以最小化分鐘數（佔用的字元）。

3. 最小化時間：

   • 每次收集所有類型的 k 個字元時，我們都會透過比較視窗的大小來追蹤所需的最少分鐘數。

時間複雜度：

• 計算字元最初需要 O(n)。
• 滑動視窗操作需要 O(n)，因為左右指標都在字串上移動一次。
• 整體時間複雜度為 O(n)。

邊緣情況：

• 如果 k == 0，則回傳 0。
• 如果不可能取出每個字元的 k，則傳回 -1。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

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

• 領英
• GitHub

以上是從左、右各取K個字符的詳細內容。更多資訊請關注PHP中文網其他相關文章！