Intermediate.
Put your skills to the test.

Problem summary

Replace as few letters as possible so no three consecutive letters are equal and no letter occupies more than half the positions. Try replacement letters in alphabetic order; any optimal valid password is accepted.

Constraints

2 ≤ length ≤ 5000.

Worked example

Input and output for the worked example discussed below.

cooooode

cooaoode

Solution analysis

1. Let cap=floor(n/2). Every constant run of length L requires floor(L/3) edits, since its disjoint triples must each be broken. Mark every third run position.
2. At most one original letter exceeds cap. At least excess=count−cap copies of it must change. Count how many required run edits already change this letter, then mark more copies until the excess is covered. Forced edits in other letters cannot help its frequency bound.
3. Count unmarked letters before filling edits. Scan marked positions left to right and choose the first letter a…z with spare capacity, different from the original, its fixed left neighbour and any fixed unmarked right neighbour. With 26 letters, at most two saturated letters and three forbidden letters cannot exhaust the choices.
4. In cooooode, the five-o run needs one edit and its global excess is also one. Replacing the third o with a gives cooaoode, meeting both lower bounds in the same edit.

Why it works

The selected positions attain forced non-majority-run edits plus the maximum of majority-run edits and its excess; replacement constraints enforce both safety rules without extra changes.

Watch out. Breaking triples alone may leave a majority. Precount all unedited positions and ensure every marked position actually changes.

An independently written complete program with standard headers.

// The selected positions attain forced non-majority-run edits plus the maximum of majority-run edits and its
// excess; replacement constraints enforce both safety rules without extra changes.
#include<array>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
    string original;
    cin>>original;
    int length=original.size();
    int capacity=length/2;
    array<int,26>frequency{};
    for(char letter:original){
        frequency[letter-'a']++;
    }
    vector<bool>change(length);
    for(int first=0;first<length;){
        int end=first+1;
        while(end<length&&original[end]==original[first]){
            end++;
        }
        for(int index=first+2;index<end;index+=3){
            change[index]=true;
        }
        first=end;
    }
    for(int letter=0;letter<26;letter++){
        int needed=frequency[letter]-capacity;
        if(needed<=0){
            continue;
        }
        for(int index=0;index<length;index++){
            if(change[index]&&original[index]-'a'==letter){
                needed--;
            }
        }
        for(int index=0;index<length&&needed>0;index++){
            if(!change[index]&&original[index]-'a'==letter){
                change[index]=true;
                needed--;
            }
        }
    }
    frequency.fill(0);
    for(int index=0;index<length;index++){
        if(!change[index]){
            frequency[original[index]-'a']++;
        }
    }
    string answer=original;
    for(int index=0;index<length;index++){
        if(!change[index]){
            continue;
        }
        for(int letter=0;letter<26;letter++){
            char candidate=char('a'+letter);
            if(frequency[letter]==capacity||candidate==original[index]){
                continue;
            }
            if(index>0&&candidate==answer[index-1]){
                continue;
            }
            if(index+1<length&&!change[index+1]&&candidate==original[index+1]){
                continue;
            }
            answer[index]=candidate;
            frequency[letter]++;
            break;
        }
    }
    cout<<answer<<'\n';
}