We are given a string and we have to find the closest string such that no two characters in the string are same.

Consider the case where the input string is "aabcda", then there can be multiple output strings where consecutive characters are not same like:

• "babcda"
• "zabcda"
• "abacda"

Note that it may seem that the answer is "babcda" but it is not the case as if we arrange all permutations of strings in order, the answer will be "abacda". This is because the left most character is the most significant character.

This problem can be solved using a simple greedy approach which will take linear time O(N) and constant space O(1).

Greedy Approach

Basically, the problem is asking for a string in which now two consecutive characters are same. We can start traversing the string from the first character and check for each consecutive character (current character and previous character)and if both are same then we change the current character to its previous character (b to a and c to b ).

Procedure

• Traverse the whole string

• Check if str[i] and str[i+1] are equal

  • If they are unequal then keep on traversing
  • Else since we have to find the closest pair of string with unequal consecutive elements then we decrease s[i+1] element to its previous character in the alphabetic series.
  • We also have to check if s[i+1]!='a' .If it is so then we can update s[i+1]='b' because if we make it 'z' then it will not be the closest pair of string.

• Since we have made the conversion and made every two pair of consecutive elements of the string unequal so now we can print the new string.

Special Case

If the current element and the previous element are both a and a then we can change the current element to b.

Examples

Input:

aabcda

Output:

abacda

Here when we traverse the string aabcda we first check if s[0] && s[1] are equal or not.Since both are equal (a and a) then we move to s[1] and change it to b by converting s[i] into type int and adding 1 to it to convert it into b.Now we check for s[1] and s[2] since both are again equal hence we convert s[2] into a by converting b into type int (which is its ASCII code) and we do an decrement in its ASCII code and again convert it into a.Now we similarly check for other consecutive elements but all are different from their previous character hence we can print the new string.

Code

Following is the C++ implementation of our above approach:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    //input the string
    string str;
    cin>>str;
    //length of the string
    int len=s.length();

    //traversing the string
    for(int i=1;i<len;i++)
    {
        //if the current element and the previous element are same
        if(str[i]==str[i-1])
        {
            //then we change the current element to its previous character
            int ch=str[i]-1;
            //if current character is a then we change it to b
            if(ch<97 || ch<65)
            {
                ch=ch+2;
            }
            str[i]=(char)ch;
        }
    }
    //printing the character
    cout<<str;
}

Input:

aaaaa

Output:

ababa

Time and Space Complexity

Since we are traversing the whole string and comparing only elements of the string then the time complexity will be O(no of characters in string)

O(n) where n is the number of characters in the strings

Since we are not taking any extra space for the above algorithm hence the space complexity of the program will be o(constant space)

Space complexity: O(1)