二.進階

1.套路

2.題目描述

1.給你一個字符串 s 。它可能包含任意數量的 '*' 字符。你的任務是刪除所有的 '*' 字符。
當字符串還存在至少一個 '*' 字符時，你可以執行以下操作：

• 刪除最左邊的 '*' 字符，同時刪除該星號字符左邊一個字典序 最小的字符。如果有多個字典序最小的字符，你可以刪除它們中的任意一個。
  請你返回刪除所有 '*' 字符以后，剩余字符連接而成的 字典序最小 的字符串(答案)。

3.學習經驗

1. 3170. 刪除星號以后字典序最小的字符串(中等，學習)

思想

1.給你一個字符串 s 。它可能包含任意數量的 '*' 字符。你的任務是刪除所有的 '*' 字符。
當字符串還存在至少一個 '*' 字符時，你可以執行以下操作：

• 刪除最左邊的 '*' 字符，同時刪除該星號字符左邊一個字典序 最小 的字符。如果有多個字典序最小的字符，你可以刪除它們中的任意一個。
  請你返回刪除所有 '*' 字符以后，剩余字符連接而成的 字典序最小 的字符串。
  2.此題和[[六.棧#7. 3412. 計算字符串的鏡像分數(中等)]]一樣，小寫字母就可以開二十六個棧，分別記錄每種字母的下標，此題難點在于同時刪除該星號字符左邊一個字典序 最小 的字符,即找到第一個下標棧不為空的字母，這就是要刪除的位置，彈出棧頂刪除完得到最終的棧后，先把保留下標合并到數組中，然后排序，最終賦值給結果
  3.可以優化為把待刪除的位置變成*號，然后直接調用字符串的remove和erase函數刪除*號即可，更快捷

代碼

合并獲取保留下標，然后排序，最后賦值給結果

class Solution {
public:string clearStars(string s) {int n = s.size();vector<vector<int>> stk(26);for (int i = 0; i < n; ++i) {int j = s[i] - 'a';if (s[i] != '*')stk[j].push_back(i);else {for (auto& st : stk) {if (!st.empty()) {st.pop_back();break;}}}}// 保留的下標vector<int> idx;// 先合并for (auto& st : stk)idx.insert(idx.end(), st.begin(), st.end());// 再排序sort(idx.begin(), idx.end());int m = idx.size();string res(m, '\0');for (int i = 0; i < m; ++i) {res[i] = s[idx[i]];}return res;}
};

把待刪除的位置變成*號，然后直接調用字符串的remove和erase函數刪除*號:

class Solution {
public:string clearStars(string s) {int n = s.size();vector<vector<int>> stk(26);for (int i = 0; i < n; ++i) {int j = s[i] - 'a';if (s[i] != '*')stk[j].push_back(i);else {for (auto& st : stk) {if (!st.empty()) {s[st.back()] = '*'; // 變成'*'號st.pop_back();break;}}}}// remove+earse方法刪除所有'*'號s.erase(remove(s.begin(), s.end(), '*'), s.end());return s;}
};

三.鄰項消除

1.套路

2.題目描述

3.學習經驗

1.遇到某個連續子串要刪除，即遇到最后一項，判斷棧頂以下幾個元素是否匹配該子串，匹配則不斷彈出棧，否則最后一項入棧
2.遇到只能用一種連續字符串構造與還原問題[[六.棧#5. 1003. 檢查替換后的詞是否有效(中等)]]

1. 2696. 刪除子串后的字符串最小長度(簡單)

2696. 刪除子串后的字符串最小長度 - 力扣（LeetCode）

思想

1.給你一個僅由 大寫 英文字符組成的字符串 s 。
你可以對此字符串執行一些操作，在每一步操作中，你可以從 s 中刪除 任一個 "AB" 或 "CD" 子字符串。
通過執行操作，刪除所有 "AB" 和 "CD" 子串，返回可獲得的最終字符串的 最小 可能長度。
注意，刪除子串后，重新連接出的字符串可能會產生新的 "AB" 或 "CD" 子串。
2.此題就是遇到B，棧頂為A則出棧A,否則入B,遇到D，棧頂為C則出棧C,否則入D,其他字符均入棧

代碼

class Solution {
public:int minLength(string s) {int n = s.size();vector<char> stk;for (auto& ch : s) {if (ch == 'B') {if (!stk.empty() && stk.back() == 'A')stk.pop_back();elsestk.push_back(ch);} else if (ch == 'D') {if (!stk.empty() && stk.back() == 'C')stk.pop_back();elsestk.push_back(ch);} elsestk.push_back(ch);}return (int)stk.size();}
};

2. 1047. 刪除字符串中的所有相鄰重復項(簡單)

1047. 刪除字符串中的所有相鄰重復項 - 力扣（LeetCode）

思想

1.給出由小寫字母組成的字符串 s，重復項刪除操作會選擇兩個相鄰且相同的字母，并刪除它們。
在 s 上反復執行重復項刪除操作，直到無法繼續刪除。
在完成所有重復項刪除操作后返回最終的字符串。答案保證唯一。
2.待入棧的每個字符，棧不為空且棧頂等于該字符則棧頂出棧，否則該字符入棧

代碼

class Solution {
public:string removeDuplicates(string s) {int n = s.size();string stk;for (auto& ch : s) {if (!stk.empty() && stk.back() == ch)stk.pop_back();elsestk.push_back(ch);}return stk;}
};

3. 1544. 整理字符串(簡單)

1544. 整理字符串 - 力扣（LeetCode）

思想

1.給你一個由大小寫英文字母組成的字符串 s 。
一個整理好的字符串中，兩個相鄰字符 s[i] 和 s[i+1]，其中 0<= i <= s.length-2 ，要滿足如下條件:

• 若 s[i] 是小寫字符，則 s[i+1] 不可以是相同的大寫字符。
• 若 s[i] 是大寫字符，則 s[i+1] 不可以是相同的小寫字符。
  請你將字符串整理好，每次你都可以從字符串中選出滿足上述條件的 兩個相鄰 字符并刪除，直到字符串整理好為止。
  請返回整理好的 字符串 。題目保證在給出的約束條件下，測試樣例對應的答案是唯一的。
  **注意：空字符串也屬于整理好的字符串，盡管其中沒有任何字符。

代碼

class Solution {
public:string makeGood(string s) {int n = s.size();string stk;for (auto& ch : s) {if (!stk.empty() &&((ch >= 'A' && ch <= 'Z' && ch - 'A' + 'a' == stk.back()) ||(ch >= 'a' && ch <= 'z' && ch - 'a' + 'A' == stk.back())))stk.pop_back();elsestk.push_back(ch);}return stk;}
};

4. 3561. 移除相鄰字符(中等)

3561. 移除相鄰字符 - 力扣（LeetCode）

思想

1.給你一個由小寫英文字母組成的字符串 s。
你 必須 在字符串 s 中至少存在兩個 連續 字符時，反復執行以下操作：

• 移除字符串中 最左邊 的一對按照字母表 連續 的相鄰字符（無論是按順序還是逆序，例如 'a' 和 'b'，或 'b' 和 'a'）。
• 將剩余字符向左移動以填補空隙。
  當無法再執行任何操作時，返回最終的字符串。
  **注意：字母表是循環的，因此 'a' 和 'z' 也視為連續。

代碼

class Solution {
public:string resultingString(string s) {int n = s.size();string stk;for (auto& ch : s) {int i = ch - 'a';if (!stk.empty() && ((i + 1) % 26 == (stk.back() - 'a') ||(i - 1 + 26) % 26 == (stk.back() - 'a')))stk.pop_back();elsestk.push_back(ch);}return stk;}
};

優化按照字母表 連續 的相鄰字符（無論是按順序還是逆序)的判斷方法:

abs(ch-stk.back())==1 || abs(ch-stk.back())==25

5. 1003. 檢查替換后的詞是否有效(中等)

1003. 檢查替換后的詞是否有效 - 力扣（LeetCode）

思想

1.給你一個字符串 s ，請你判斷它是否 有效 。
字符串 s 有效 需要滿足：假設開始有一個空字符串 t = "" ，你可以執行 任意次 下述操作將 t 轉換為 s ：

• 將字符串 "abc" 插入到 t 中的任意位置。形式上，t 變為 tleft + "abc" + tright，其中 t == tleft + tright 。注意，tleft 和 tright 可能為 空 。
  如果字符串 s 有效，則返回 true；否則，返回 false。
  2.此題特征為只運行插入合法子串"abc",從而構造出s,現在讓我們去通過s反過來還原為t,即模式識別到這個合法子串就彈出

代碼

class Solution {
public:bool isValid(string s) {int n = s.size();string stk;for (auto& ch : s) {if (stk.size() >= 2 && ch == 'c' && stk.back() == 'b' &&stk[stk.size() - 2] == 'a') {stk.pop_back();stk.pop_back();} elsestk.push_back(ch);}return stk.empty();}
};