Rearrange characters in a sorted string such that no pair of adjacent characters are the same | C ++ program for the above approach ; Function to check if a string S contains pair of adjacent characters that are equal or not ; Traverse the string S ; If S [ i ] and S [ i + 1 ] are equal ; Otherwise , return false ; Function to rearrange characters of a string such that no pair of adjacent characters are the same ; Initialize 3 variables ; Iterate until k < N ; If S [ i ] is not equal to S [ j ] ; Increment i and j by 1 ; If j equals k and increment the value of K by 1 ; Else ; If S [ j ] equals S [ k ] ; Increment k by 1 ; Else ; Swap ; Increment i and j by 1 ; If j equals k ; Increment k by 1 ; Function to rearrange characters in a string so that no two adjacent characters are same ; If string is already valid ; If size of the string is 2 ; Function Call ; Reversing the string ; Function Call ; If the string is valid ; Otherwise ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isAdjChar ( string & s ) { for ( int i = 0 ; i < s . size ( ) - 1 ; i ++ ) { if ( s [ i ] == s [ i + 1 ] ) return true ; } return false ; } void rearrangeStringUtil ( string & S , int N ) { int i = 0 , j = 1 , k = 2 ; while ( k < N ) { if ( S [ i ] != S [ j ] ) { i ++ ; j ++ ; if ( j == k ) { k ++ ; } } else { if ( S [ j ] == S [ k ] ) { k ++ ; } else { swap ( S [ k ] , S [ j ] ) ; i ++ ; j ++ ; if ( j == k ) { k ++ ; } } } } } string rearrangeString ( string & S , int N ) { if ( isAdjChar ( S ) == false ) { return S ; } if ( S . size ( ) == 2 ) return " - 1" ; rearrangeStringUtil ( S , N ) ; reverse ( S . begin ( ) , S . end ( ) ) ; rearrangeStringUtil ( S , N ) ; if ( isAdjChar ( S ) == false ) { return S ; } return " - 1" ; } int main ( ) { string S = " aaabc " ; int N = S . length ( ) ; cout << rearrangeString ( S , N ) ; return 0 ; }