本番に書いたコードの実装が悪すぎたので書き直し
問題概要
原文 → Loading...
文字列 が与えられる。この文字列に対して、あるふたつの文字を選んで swap することが一度だけできる。同じアルファベットを最大で何連続させられるか答えよ。
解説
まずランレングス圧縮をする。あとはそれぞれの要素に対して次に示すものを計算して max をとればよい。
- swap する前の長さ
- swap する前の長さ + 1 (ただし、この結果が文字の登場回数より多くなってはいけない)
- aa...a b aa...a のように真ん中が 1 文字だけ異なる場合を考慮するために、(左の要素の長さ) + (右の要素の長さ) + 1 を計算する。ただし、この結果が文字の登場回数より多くなってはいけない。
ソースコード
class Solution { public: int maxRepOpt1(string text) { vector< pair<char, int> > rle; vector<int> cnt(26); for(auto c : text) { if(rle.empty() or rle.back().first != c) rle.emplace_back(c, 1); else rle.back().second++; cnt[c - 'a']++; } int N = rle.size(), ans = 0; for(int i=0; i<N; i++) { int id = rle[i].first - 'a'; ans = max(ans, min(cnt[id], rle[i].second + 1)); } for(int i=1; i+1<N; i++) { if(rle[i-1].first == rle[i+1].first and rle[i].second == 1) { int id = rle[i-1].first - 'a'; ans = max(ans, min(cnt[id], rle[i-1].second + rle[i+1].second + 1)); } } return ans; } };
これくらい簡潔な実装を思いつきたかったなあ。