文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

如果字符串中的所有字符都相同，那么這個(gè)字符串是單字符重復(fù)的字符串。

給你一個(gè)字符串 text，你只能交換其中兩個(gè)字符一次或者什么都不做，然后得到一些單字符重復(fù)的子串。
返回其中最長的子串的長度。

示例 1： 輸入：text = "ababa" 輸出：3示例 2： 輸入：text = "aaabaaa" 輸出：6示例 3： 輸入：text = "aaabbaaa" 輸出：4示例 4： 輸入：text = "aaaaa" 輸出：5示例 5： 輸入：text = "abcdef" 輸出：1提示： 1 <= text.length <= 20000 text 僅由小寫英文字母組成。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/swap-for-longest-repeated-character-substring
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 把每個(gè)字符，每段的開始結(jié)束位置存起來
• 在檢查相鄰的段之間的間距是不是1，進(jìn)行分類討論

class Solution { public:int maxRepOpt1(string text) {text.push_back('-');//方便代碼處理vector<vector<vector<int>>> p(26);// 存放每個(gè)字符每個(gè)連續(xù)段的 {開始位置，結(jié)束位置}char prev = text[0];int start = 0, ans = 1;for(int i = 0; i < text.size(); ++i){if(text[i] != prev){p[prev-'a'].push_back({start, i-1});ans = max(ans, i-start);//什么都不做的情況下的最大長度start = i;prev = text[i];}}for(int i = 0; i < 26; ++i){int len = p[i].size();//有多少段該字符for(int j = 1; j < len; ++j){int prevEnd = p[i][j-1][1];int n1 = p[i][j-1][1]-p[i][j-1][0]+1;int curStart = p[i][j][0];int n2 = p[i][j][1]-p[i][j][0]+1;if(curStart-prevEnd == 2)//隔一個(gè)字符{ans = max(ans, n1+n2+(len>2 ? 1 : 0));} //3段及以上，可以在多添加1個(gè)字符進(jìn)來else//間隔多個(gè)字符{ans = max(ans, max(n1+1, n2+1));} // 兩段不能聯(lián)通，只能過去1個(gè)字符}}return ans;} };

20 ms 11.7 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1156. 单字符重复子串的最大长度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。