Sort a string lexicographically using triple cyclic shifts | C ++ Program for sorting a string using cyclic shift of three indices ; Store the indices which haven 't attained  its correct position ; Store the indices undergoing cyclic shifts ; If the element is not at it 's correct position ; Check if all 3 indices can be placed to respective correct indices in a single move ; If the i - th index is still not present in its correct position , store the index ; To check if swapping two indices places them in their correct position ; for ( int i = 0 ; i < indices . size ( ) ; i ++ ) { cout << indices [ i ] [ 0 ] << " ▁ " << indices [ i ] [ 1 ] << " ▁ " << indices [ i ] [ 2 ] << endl ; } ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void sortString ( vector < int > & arr , int n , int moves ) { vector < int > pos ; vector < vector < int > > indices ; bool flag = false ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] != i ) { if ( arr [ arr [ arr [ i ] ] ] == i && arr [ arr [ i ] ] != i ) { int temp = arr [ arr [ i ] ] ; indices . push_back ( { i , arr [ i ] , arr [ arr [ i ] ] } ) ; swap ( arr [ i ] , arr [ arr [ i ] ] ) ; swap ( arr [ i ] , arr [ temp ] ) ; } } if ( arr [ i ] != i ) { pos . push_back ( i ) ; } } for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] != i ) { int pos1 = i , pos2 = arr [ i ] ; int pos3 = arr [ arr [ i ] ] ; if ( pos3 != pos1 ) { indices . push_back ( { pos1 , pos2 , pos3 } ) ; swap ( arr [ pos1 ] , arr [ pos2 ] ) ; swap ( arr [ pos1 ] , arr [ pos3 ] ) ; pos . erase ( find ( pos . begin ( ) , pos . end ( ) , pos2 ) ) ; pos . erase ( find ( pos . begin ( ) , pos . end ( ) , pos3 ) ) ; if ( arr [ pos1 ] == pos1 ) { pos . erase ( find ( pos . begin ( ) , pos . end ( ) , pos1 ) ) ; } } else { if ( pos3 == * pos . begin ( ) ) { if ( * pos . begin ( ) != pos . back ( ) ) { auto it = ++ pos . begin ( ) ; pos3 = * ( it ) ; if ( * it != pos . back ( ) && pos3 == pos2 ) { pos3 = * ( ++ it ) ; } else if ( * it == pos . back ( ) && pos3 == pos2 ) { flag = true ; break ; } } else { flag = true ; break ; } } indices . push_back ( { pos1 , pos2 , pos3 } ) ; swap ( arr [ pos1 ] , arr [ pos2 ] ) ; swap ( arr [ pos1 ] , arr [ pos3 ] ) ; pos . erase ( find ( pos . begin ( ) , pos . end ( ) , pos2 ) ) ; } } if ( arr [ i ] != i ) { i -- ; } } if ( flag == true || indices . size ( ) > moves ) { cout << " Not ▁ Possible " << endl ; } else { cout << indices . size ( ) << endl ; } } int main ( ) { string s = " adceb " ; vector < int > arr ; for ( int i = 0 ; i < s . size ( ) ; i ++ ) { arr . push_back ( s [ i ] - ' a ' ) ; } sortString ( arr , s . size ( ) , floor ( s . size ( ) / 2 ) ) ; }