2516。從左右各取K個字符

難度：中等

主題：哈希表、字符串、滑動窗口

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

返回最少獲取至少 k 個字符所需的分鐘數(shù)，如果不可能獲取每個字符的k 個，則返回-1角色。

示例1：

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

示例2：

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

約束：

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

提示：

1. 首先計算每個字符的出現(xiàn)頻率并檢查是否可能。
2. 如果從左側取x個字符，那么從右側最少需要取多少個字符？對 0 ≤ x ≤ s.length 范圍內(nèi)的所有 x 值求此值。
3. 使用兩指針方法來避免多次計算相同的信息。

解決方案：

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

問題分解：

• 給定一個僅包含 'a'、'b' 和 'c' 的字符串 s。
• 我們需要從字符串的最左邊或最右邊的字符中獲取每個字符至少出現(xiàn)的 k 次。
• 我們需要確定實現(xiàn)此目標所需的最小分鐘數(shù)，如果不可能，則返回 -1。

方法：

1. 初步檢查：

   • 如果 k == 0，我們可以直接返回 0，因為不需要任何字符。
   • 如果 k 超過字符串中任意字符出現(xiàn)的次數(shù)，則立即返回 -1。

2. 頻率計數(shù):

   • 我們需要統(tǒng)計 'a'、'b' 和 'c' 在字符串 s 中出現(xiàn)了多少次，以確保甚至可以收集到每個字符的 k 個。

3. 滑動窗口技術:

   • 使用帶有兩個指針（左和右）的滑動窗口方法。
   • 維護兩個指針，并從字符串兩端滑動它們以收集所需的字符。
   • 對于從左側取出的每個字符，計算需要從右側取出的最少字符數(shù)才能滿足要求。

4. 優(yōu)化：

   • 我們可以在擴展或收縮窗口時跟蹤字符計數(shù)，而不是重復地重新計算每個窗口的字符計數(shù)。

讓我們用 PHP 實現(xiàn)這個解決方案：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”的出現(xiàn)次數(shù)，以確?？梢允占辽?k 個字符。
   • 如果任意字符數(shù)小于 k，則返回 -1。

2. 滑動窗口:

   • 我們使用兩個指針（左和右）從兩端創(chuàng)建一個滑動窗口。
   • 我們通過移動右側指針來擴展窗口并增加遇到的字符數(shù)。
   • 一旦當前窗口中的每個字符至少有 k 個，我們就會嘗試從左側縮小窗口以最小化分鐘數(shù)（占用的字符）。

3. 最小化時間：

   • 每次收集所有類型的 k 個字符時，我們都會通過比較窗口的大小來跟蹤所需的最少分鐘數(shù)。

時間復雜度：

• 計算字符最初需要 O(n)。
• 滑動窗口操作需要 O(n)，因為左右指針都在字符串上移動一次。
• 總體時間復雜度為 O(n)。

邊緣情況：

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

聯(lián)系鏈接

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

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

• 領英
• GitHub

以上是從左、右各取K個字符的詳細內(nèi)容。更多信息請關注PHP中文網(wǎng)其他相關文章！