如果有不明白的，請加文末QQ群。

本文涉及知識點

最長公共前綴 動態規劃
動態規劃匯總

LeetCode 2430. 對字母串可執行的最大刪除數

給你一個僅由小寫英文字母組成的字符串 s 。在一步操作中，你可以：
刪除 整個字符串 s ，或者
對于滿足 1 <= i <= s.length / 2 的任意 i ，如果 s 中的 前 i 個字母和接下來的 i 個字母 相等 ，刪除 前 i 個字母。
例如，如果 s = “ababc” ，那么在一步操作中，你可以刪除 s 的前兩個字母得到 “abc” ，因為 s 的前兩個字母和接下來的兩個字母都等于 “ab” 。
返回刪除 s 所需的最大操作數。
示例 1：
輸入：s = “abcabcdabc”
輸出：2
解釋：

• 刪除前 3 個字母（“abc”），因為它們和接下來 3 個字母相等。現在，s = “abcdabc”。
• 刪除全部字母。
  一共用了 2 步操作，所以返回 2 。可以證明 2 是所需的最大操作數。
  注意，在第二步操作中無法再次刪除 “abc” ，因為 “abc” 的下一次出現并不是位于接下來的 3 個字母。
  示例 2：
  輸入：s = “aaabaab”
  輸出：4
  解釋：
• 刪除第一個字母（“a”），因為它和接下來的字母相等。現在，s = “aabaab”。
• 刪除前 3 個字母（“aab”），因為它們和接下來 3 個字母相等。現在，s = “aab”。
• 刪除第一個字母（“a”），因為它和接下來的字母相等。現在，s = “ab”。
• 刪除全部字母。
  一共用了 4 步操作，所以返回 4 。可以證明 4 是所需的最大操作數。
  示例 3：
  輸入：s = “aaaaa”
  輸出：5
  解釋：在每一步操作中，都可以僅刪除 s 的第一個字母。
  提示：
  1 <= s.length <= 4000
  s 僅由小寫英文字母組成

最長公共前綴

n = s.length
先預處理出最長公共前綴lcp，時間復雜度：O(nn)。

動態規劃的狀態表示

dp[i]記錄 s[i… ]的最大操作次數。空間復雜度: O(n)

動態規劃的填表順序

dp[i] = 1
for(len =1 ; i+len*2 <=n ;len++)
如果lcp[i][i+len] >= len 則 dp[i] = max(dp[i],dp[i+len]+1);
單個狀態轉移的時間復雜度：O(n)
總時間復雜度：O(nn)

動態規劃的初始值

全為1

動態規劃的填表順序

i = n -1 to 0

動態規劃的返回值

dp[0]

代碼

核心代碼

//最長公共前綴(Longest Common Prefix)
class CLCP
{
public:CLCP(const string& str1, const string& str2){m_dp.assign(str1.length() , vector<int>(str2.length()));//str1[j...)和str2[k...]比較時, j和k不斷自增，總有一個先到達末端for (int i = 0; i < str1.length(); i++){//枚舉str2 先到末端 str1[i]和str2.back對應m_dp[i][str2.length() - 1] = (str1[i] == str2.back());for (int j = i-1 ; j >= 0 ; j-- ){const int k = str2.length() - 1 - (i-j);if (k < 0){break;}if (str1[j] == str2[k]){m_dp[j][k] = 1 + m_dp[j + 1][k + 1];}}			}for (int i = 0; i < str2.length(); i++){//枚舉str1 先到末端 str2[i]和str1.back對應m_dp[str1.length()-1][i] = (str1.back() == str2[i]);for (int j = i - 1; j >= 0; j--){const int k = str1.length() - 1 - (i-j);if (k < 0){break;}if (str1[k] == str2[j]){m_dp[k][j] = 1 + m_dp[k + 1][j + 1];}}}}vector<vector<int>> m_dp;
};template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{*seft = max(*seft, other);
}
class Solution {
public:int deleteString(string s) {CLCP lcp(s, s);vector<int> dp(s.length(), 1);for (int i = s.length() - 1; i >= 0; i--) {for (int len = 1; i + len * 2 <= s.length(); len++) {if (lcp.m_dp[i][i + len] >= len) {MaxSelf(&dp[i], dp[i + len] + 1);}}}return dp.front();}
};

單元測試

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{	string s;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){s = "abcabcdabc";auto res = Solution().deleteString(s);AssertEx(2, res);}TEST_METHOD(TestMethod01){s = "aaabaab";auto res = Solution().deleteString(s);AssertEx(4, res);}TEST_METHOD(TestMethod02){s = "aaaaa";auto res = Solution().deleteString(s);AssertEx(5, res);}};
}

擴展閱讀

視頻課程

先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

相關推薦

我想對大家說的話
《喜缺全書算法冊》以原理、正確性證明、總結為主。
按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
有效學習：明確的目標 及時的反饋 拉伸區（難度合適） 專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。