Competitive Programming

Codeforces 665 C. Simple Strings

Problem Statement:

http://codeforces.com/problemset/problem/665/C

Approach :
Simply dissociate the whole string into sequences that have similar consecutive characters.
• If there are odd numbers of consecutive characters simply replace alternative characters. For example, “aaaaa” becomes “ababa”.
• If there are even numbers of character do the same as above. However check that the last character of the sequence and the character in the next sequence don’t match.

Solution :

#include<bits/stdc++.h>;
using namespace std ;
//-------------------------------
typedef long long ll ;
typedef vector<int> vi ;
typedef pair<int,int> ii ;
//-------------------------------
#define _CRT_SECURE_NO_WARNINGS
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(ll i=(a) ; (i)<(b) ; ++i)
#define inf 2000000000
#define endl "\n"
#define de(x) cerr<<#x<<" is "<<x<<endl;
#define max(a,b) ( (a>b) ? (a) : (b)  )
#define min(a,b) ( (a<b) ? (a) : (b)  )
//------------------------------
int ri() { char c = getchar(); while(c<'0' || c>'9') c=getchar(); int ret = 0; while(c>='0' && c<='9') { ret=10*ret+c-48; c=getchar(); } return ret; }

char getNextChar(char x)
{
    int nu = x - 'a' ;
    nu++ ;
    nu %= 26 ;
    return (char)('a'+nu) ;
}
string s;
int main()
{
    cin << s ;
    int i =0 ;
    string ans = "" ;
    while(i<s.size())
    {
        string temp="";
        char x = s[i] ;
        char nxt = getNextChar(s[i]) ;
        while(i<s.size() && s[i]==x)
        {
            temp += s[i++];
        }
        for(int j=1;j<temp.size();j+=2)
            temp[j] = nxt;
        ans += temp;
    }
    rep(i,0,ans.size()-1)
    if(ans[i] == ans[i+1])
        ans[i] = getNextChar(ans[i+1]);
    cout << ans << endl ;

}

Leave a comment