Sort a string lexicographically by reversing a substring | Java program for the above approach ; Function to find the substring in S required to be reversed ; Stores the size of the string ; Stores the starting point of the substring ; Iterate over the string S while i < N ; Increment the value of i ; Stores the ending index of the substring ; If start <= 0 or i >= N ; If start >= 1 and i <= N ; Return the boolean value ; If start >= 1 ; Return the boolean value ; If i < N ; Return true if S [ start ] is less than or equal to S [ i ] ; Otherwise ; Function to check if it is possible to sort the string or not ; Stores the starting and the ending index of substring ; Stores whether it is possible to sort the substring ; Traverse the range [ 1 , N ] ; If S [ i ] is less than S [ i - 1 ] ; If flag stores true ; If adjust ( S , i , start , end ) return false ; Print - 1 ; Unset the flag ; Otherwise ; Print - 1 ; If start is equal to - 1 ; Update start and end ; Print the value of start ; Driver code
import java . util . * ; import java . lang . * ; class GFG { static int i , start , end ; static boolean adjust ( String S ) { int N = S . length ( ) ; start = i - 1 ; while ( i < N && S . charAt ( i ) < S . charAt ( i - 1 ) ) { i ++ ; } end = i - 1 ; if ( start <= 0 && i >= N ) return true ; if ( start >= 1 && i <= N ) { return ( S . charAt ( end ) >= S . charAt ( start - 1 ) && S . charAt ( start ) <= S . charAt ( i ) ) ; } if ( start >= 1 ) { return S . charAt ( end ) >= S . charAt ( start - 1 ) ; } if ( i < N ) { return S . charAt ( start ) <= S . charAt ( i ) ; } return false ; } static void isPossible ( String S , int N ) { start = - 1 ; end = - 1 ; boolean flag = true ; for ( i = 1 ; i < N ; i ++ ) { if ( S . charAt ( i ) < S . charAt ( i - 1 ) ) { if ( flag ) { if ( adjust ( S ) == false ) { System . out . println ( - 1 ) ; return ; } flag = false ; } else { System . out . println ( - 1 ) ; return ; } } } if ( start == - 1 ) { start = end = 1 ; } System . out . println ( start + " ▁ " + end ) ; } public static void main ( String [ ] args ) { String S = " abcyxuz " ; int N = S . length ( ) ; isPossible ( S , N ) ; } }