Rearrange characters in a sorted string such that no pair of adjacent characters are the same | Java 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
import java . util . * ; class GFG { static char [ ] S = " aaabc " . toCharArray ( ) ; static boolean isAdjChar ( ) { for ( int i = 0 ; i < S . length - 1 ; i ++ ) { if ( S [ i ] == S [ i + 1 ] ) return true ; } return false ; } static void rearrangeStringUtil ( 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 ( k , j ) ; i ++ ; j ++ ; if ( j == k ) { k ++ ; } } } } } static void swap ( int i , int j ) { char temp = S [ i ] ; S [ i ] = S [ j ] ; S [ j ] = temp ; } static String rearrangeString ( int N ) { if ( isAdjChar ( ) == false ) { return String . valueOf ( S ) ; } if ( S . length == 2 ) return " - 1" ; rearrangeStringUtil ( N ) ; reverse ( ) ; rearrangeStringUtil ( N ) ; if ( isAdjChar ( ) == false ) { return String . valueOf ( S ) ; } return " - 1" ; } static void reverse ( ) { int l , r = S . length - 1 ; for ( l = 0 ; l < r ; l ++ , r -- ) { char temp = S [ l ] ; S [ l ] = S [ r ] ; S [ r ] = temp ; } } public static void main ( String [ ] args ) { int N = S . length ; System . out . print ( rearrangeString ( N ) ) ; } }