原題鏈接

鏈接：https://www.nowcoder.net/questionTerminal/fcd645af2750401588d9e92aea05d630

有一個僅包含’a’和’b’兩種字符的字符串s，長度為n，每次操作可以把一個字符做一次轉換（把一個’a’設置為’b’，或者把一個’b’置成’a’)；但是操作的次數有上限m，問在有限的操作數范圍內，能夠得到最大連續的相同字符的子串的長度是多少。

輸入描述:

第一行兩個整數 n , m (1<=m<=n<=50000)，第二行為長度為n且只包含’a’和’b’的字符串s。

輸出描述:

輸出在操作次數不超過 m 的情況下，能夠得到的 最大連續 全’a’子串或全’b’子串的長度。 示例：

輸入

8 1 aabaabaa

輸出

5

說明

把第一個 'b' 或者第二個 'b' 置成 'a'，可得到長度為 5 的全 'a' 子串。

————————————?? 分界線————————————————

分析：

該字符串非 a 即 b 也就是說在區間 l~r之間把所有字符變為 a 所需的步驟數是 該區間內 b 的數量。反之亦然. 用數組 count[i] 表示 字符串中位置區間 0~i 包含的 a 的個數 則 區間 l~r 的 a 的個數為 count[r]-count[l-1] b 的個數用 a 的個數算出 即 區間 l~r 的 b 的個數為 r+1-count[r]-(l+1-1-count[l-1])=r+1-count[r]-l+count[l-1]在區間 l~r 的 a 和 b 的個數已知的情況下 若 區間長度step內的 a 的個數 <= m 則 可以通過 m 個步驟 產生 長度為step的字符串 b 若 區間長度step內的 b 的個數 <= m 則 可以通過 m 個步驟 產生 長度為step的字符串 a歸納為 ：若 區間長度step內的 b 或 a 的個數 <= m 則 可以通過 m 個步驟 產生 長度為step的字符串這樣 就可以直接計算出一個字符串長度（區間長度step）是否可行，因此不需要進行遞推，可以直接進行二分搜索，得到最大長度。 檢查一個長度step是否可行的時間復雜度為O(n),二分搜索的時間復雜度為O(log n)。 因此，該方法總的時間復雜度為 O(n*log n)

代碼：

#include<iostream> #include<string> #include<cstring> using namespace std; int count[50005]; int n,m; int ans=0;//檢查當前區間長度(step)是否能在 m 個步驟內實現全 a 或 全 b bool func(int step){for(int i=0;i+step<n;i++){if(m>=step+1-(count[i+step]-count[i-1]))return true; //檢查 a 公式 m>=區間內 b 的個數 if(m>=count[i+step]-count[i-1])return true; //檢查 b 公式： m>=區間內 a 的個數 }return false; }int main(){cin>>n>>m;string str;cin>>str;//輸入并計算出 count 數組 int sum=0;for(int i=0;i<str.size();i++){if(str[i]=='a')count[i]=++sum;else count[i]=sum;}//二分搜索最大區間值 int l=0,r=n-1,mid; while(l<r){mid=l+(r-l)/2;if(func(mid)){l=mid+1;}else r=mid;}ans=max(ans,l);cout<<ans<<endl;return 0;}

總結

以上是生活随笔為你收集整理的题解-今日头条2018校招后端方向（第四批）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。