在給定條件下最大化從字串中刪除的字元數
在這個問題中,我們需要刪除字串中的最大字元數,如果相鄰字元是前一個字元。
我們可以找到每個字元的出現次數,並檢查其任何相鄰字元是否為前一個字元,我們可以刪除該特定字元。
問題陳述 - 我們給定一個包含 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)
在這裡,我們以反向順序刪除每個字元以最大化刪除。如果我們以隨機順序從字串中刪除字元,我們可能無法刪除最大字元。
廣告