Problem: 1750. 刪除字符串兩端相同字符后的最短長度1750. 刪除字符串兩端相同字符后的最短長度 1750. 刪除字符串兩端相同字符后的最短長度

思路

雙指針遍歷

解題過程

模擬題目描述的過程，使用指針 l, r 指向首尾兩端。

如果相同就向中心移動。為了盡可能的刪除多余的前綴和后綴，需要將兩側字符相等都刪除。

如果不同，當前長度就是最短長度，直接返回。

實現過程

雙指針初始化：l 指向字符串開頭，r 指向結尾。

循環條件：當 l < r 時循環（表示還有可操作的空間）。

字符匹配：

若 s[l] == s[r]：刪除這對字符（l++, r--），然后跳過所有連續的相同字符：

左側跳過：while (s[l] == s[l - 1] && l <= r) l++（刪除前綴的連續相同字符）。

右側跳過：while (s[r] == s[r + 1] && l <= r) r--（刪除后綴的連續相同字符）。

若 s[l] != s[r]：無法繼續刪除，直接返回剩余長度 r - l + 1。

循環結束處理：

若 r < l，說明字符串被完全刪除，返回 0。

若 r == l，說明剩余一個字符，返回 1。

邊界情況思考（重要）

為什么需要在刪除連續相同字符的時候需要判斷條件 l<=r ?

• 防止越界和無效操作：在跳過連續字符時，需確保指針未交叉（l 不超過 r）。若 l > r，繼續移動指針會訪問無效內存或導致邏輯錯誤。

• 處理剩余字符：當 l == r 時，需檢查該字符是否與刪除的字符相同（可能屬于前綴或后綴的一部分）。

案例 1：字符串 "aaa"（全相同字符）

初始：l=0, r=2（字符 'a' 匹配）。

刪除兩端：l=1, r=1。

左側跳過：s[1]=='a' 且 l<=r（1<=1），l++ → l=2（此時 l>r）。

結果：返回 0（完全刪除）。

關鍵：l<=r 允許在 l==r 時進入循環，確保中間字符被正確處理。

案例 2：字符串 "aba"（中間字符不同）

初始：l=0, r=2（字符 'a' 匹配）。

刪除兩端：l=1, r=1。

左側跳過：s[1]=='b' != s[0]=='a'，不移動。

右側跳過：s[1]=='b' != s[2]=='a'，不移動。

結果：返回 1（剩余中間字符 'b'）。

案例 3：字符串 "abba"（兩對相同字符）

第一輪：l=0, r=3（'a'=='a'），刪除后 l=1, r=2。

第二輪：l=1, r=2（'b'=='b'），刪除后 l=2, r=1（此時 l>r）。

結果：返回 0（完全刪除）。

code

python

class Solution:def minimumLength(self, s: str) -> int:n = len(s)l = 0r = n - 1while l < r:cl = s[l]cr = s[r]if s[l] == s[r]:l += 1r -= 1while s[l] == s[l-1] and l<=r:l+=1while s[r] == s[r+1] and l<=r:r-=1else:return r-l+1return 0 if r<l else 1

c++

class Solution {
public:int minimumLength(string s) {int n = s.length();int l = 0, r = n - 1;while (l < r) {char cl = s[l], cr = s[r];if (cl == cr) {l++, r--;while (s[l] == s[l - 1] && l <= r)l++;while (s[r] == s[r + 1] && l <= r)r--;} else {return r - l + 1;}}return r < l ? 0 : 1;}
};

復雜度

• 時間復雜度: O(n)

• 空間復雜度: O(1)