SRM572 Div1 Easy(250) NewArenaPassword

TopCoder

NewArenaPassword

文字列の接頭辞でも接尾辞でもある文字列をborderという。長さnの文字列wが長さbのborderを持つ⇔wが周期n-bを持つ。一番多い文字以外を書き換える。

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class NewArenaPassword{public:
int minChange( string oldPassword, int K )
{
    int n = (int)oldPassword.size();
    int p = n-K;
    int ans = 0;
    for ( int i=0; i<p; i++ )
    {
        vector<int> C(256);
        int c = 0;
        for ( int j=i; j<n; j+=p )
            C[oldPassword[j]]++,
            c++;
        ans += c - *max_element(C.begin(),C.end());
    }
    return ans;
}};