hogecoder

tsutaj 競技プログラミングの記録

LeetCode Weekly Contest 149: Swap For Longest Repeated Character Substring

本番に書いたコードの実装が悪すぎたので書き直し

問題概要

原文 → Loading...

文字列  S が与えられる。この文字列に対して、あるふたつの文字を選んで 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;
    }
};

これくらい簡潔な実装を思いつきたかったなあ。