2516。從左右各取K個(gè)字元

難度：中

主題：雜湊表、字串、滑動(dòng)視窗

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

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

範(fàn)例1：

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

範(fàn)例2：

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

約束：

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

提示：

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

解：

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

問題分解：

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

方法：

1. 初步檢查：

   • 如果 k == 0，我們可以直接回傳 0，因?yàn)椴恍枰魏巫衷?
   • 如果 k 超過字串中任意字元出現(xiàn)的次數(shù)，則立即傳回 -1。

2. 頻率計(jì)數(shù):

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

3. 滑動(dòng)視窗技術(shù):

   • 使用兩個(gè)指標(biāo)（左和右）的滑動(dòng)視窗方法。
   • 維護(hù)兩個(gè)指針，並從字串兩端滑動(dòng)它們以收集所需的字元。
   • 對於從左側(cè)取出的每個(gè)字符，計(jì)算需要從右側(cè)取出的最少字符數(shù)才能滿足要求。

4. 最佳化：

   • 我們可以在擴(kuò)展或收縮視窗時(shí)追蹤字元計(jì)數(shù)，而不是重複地重新計(jì)算每個(gè)視窗的字元計(jì)數(shù)。

讓我們用 PHP 實(shí)作這個(gè)解：2516。從左右各取K個(gè)

<?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. 初始設(shè)定：

   • 我們計(jì)算整個(gè)字串中「a」、「b」和「c」的出現(xiàn)次數(shù)，以確?？梢允占辽?k 個(gè)字元。
   • 如果任意字元數(shù)小於 k，則傳回 -1。

2. 滑動(dòng)視窗:

   • 我們使用兩個(gè)指標(biāo)（左和右）從兩端建立一個(gè)滑動(dòng)視窗。
   • 我們透過移動(dòng)右側(cè)指標(biāo)來擴(kuò)展視窗並增加遇到的字元數(shù)。
   • 一旦目前視窗中的每個(gè)字元至少有 k 個(gè)，我們就會(huì)嘗試從左側(cè)縮小視窗以最小化分鐘數(shù)（佔(zhàn)用的字元）。

3. 最小化時(shí)間：

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

時(shí)間複雜度：

• 計(jì)算字元最初需要 O(n)。
• 滑動(dòng)視窗操作需要 O(n)，因?yàn)樽笥抑笜?biāo)都在字串上移動(dòng)一次。
• 整體時(shí)間複雜度為 O(n)。

邊緣情況：

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

聯(lián)絡(luò)連結(jié)

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

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

• 領(lǐng)英
• GitHub

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