在給定條件下最大化從字串中刪除的字元數


在這個問題中,我們需要刪除字串中的最大字元數,如果相鄰字元是前一個字元。

我們可以找到每個字元的出現次數,並檢查其任何相鄰字元是否為前一個字元,我們可以刪除該特定字元。

問題陳述 - 我們給定一個包含 N 個字母字元的字串。給定的任務是,我們需要刪除最大數量的字元,如果任何相鄰字元是字母表中的前一個字元,則可以刪除字串的任何字元。最後,列印刪除的字元計數。

示例

輸入

str = 'acd'

輸出

1

解釋 - 我們可以刪除 'd',因為相鄰字元是 'c'。

輸入

str = "efghijk"

輸出

6

解釋 - 我們可以刪除 'k',因為相鄰字元是 'j'。

我們可以刪除 'j',因為其相鄰字元是 'i'。

這樣,我們可以刪除除 'e' 之外的所有字元。因此,我們可以刪除 6 個字元。

輸入

str = "agnbpc";

輸出

0

解釋 - 字串的任何字元都沒有相鄰字元是字母表中的前一個字元。

方法 1

此方法將從 'z' 到 'a' 開始。我們將找到 'z'、'y'、'x' 等的所有出現次數。如果我們找到任何字母的前一個相鄰字元,我們可以刪除當前字元。

演算法

步驟 1 - 使用迴圈反向遍歷字母字元。

步驟 2 - 使用另一個巢狀迴圈遍歷字串。如果字串中的字元等於字元 p,請執行以下步驟。

步驟 3 - 檢查任何相鄰字元是否等於前一個字元;如果是,則從字串中刪除該字元,並將 q 的值減 1。

步驟 4 - 返回當前字串長度減去更新後字串長度的結果。

示例

#include <iostream>
using namespace std;

int numOfMaxCharacters(string alpha, int str_len) {
   // Traverse alphabets from 'z' to 'a'
   for (int p = 'z'; p > 'a'; p--) {
      // Traverse string
      for (int q = 0; q < alpha.size(); q++) {
         // If the character matches
         if (alpha[q] == p) {
            // Check if adjacent characters are less than the current character
            if (alpha[q - 1] == p - 1 || alpha[q + 1] == p - 1) {
               alpha.erase(q, 1);
               q = -1;
            }
         }
      }
   }
   // Return answer
   return str_len - alpha.size();
}
int main() {
   string str = "efghijk";
   // String size
   int str_len = str.size();
   cout << "The number of maximum characters that we can remove is " << numOfMaxCharacters(str, str_len);
}

輸出

The number of maximum characters that we can remove is 6

時間複雜度 - O(N),因為我們遍歷了字串。

空間複雜度 - O(1)

在這裡,我們以反向順序刪除每個字元以最大化刪除。如果我們以隨機順序從字串中刪除字元,我們可能無法刪除最大字元。

更新於:2023年8月24日

83 次檢視

開啟你的職業生涯

完成課程獲得認證

開始
廣告