Closest string such that no two consecutive characters are same
Sign up for FREE 1 month of Kindle and read all our books for free.
Get FREE domain for 1st year and build your brand new site
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[i1])
{
//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)