Sort a string lexicographically by reversing a substring | 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 ; global start , end , i 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 ; Pr - 1 ; Unset the flag ; Otherwise ; Pr - 1 ; If start is equal to - 1 ; Update start and end ; Print the value of start and end ; Driver Code
def adjust ( S , i , start , end ) : NEW_LINE INDENT N = len ( S ) NEW_LINE start = i - 1 NEW_LINE while ( i < N and S [ i ] < S [ i - 1 ] ) : NEW_LINE INDENT i += 1 NEW_LINE DEDENT end = i - 1 NEW_LINE if ( start <= 0 and i >= N ) : NEW_LINE INDENT return True , start , i , end NEW_LINE DEDENT if ( start >= 1 and i <= N ) : NEW_LINE INDENT return ( S [ end ] >= S [ start - 1 ] and S [ start ] <= S [ i ] ) , start , i , end NEW_LINE DEDENT if ( start >= 1 ) : NEW_LINE INDENT return ( S [ end ] >= S [ start - 1 ] ) , start , i , end NEW_LINE DEDENT if ( i < N ) : NEW_LINE INDENT return ( S [ start ] <= S [ i ] ) , start , i , end NEW_LINE DEDENT return False , start , i , end NEW_LINE DEDENT def isPossible ( S , N ) : NEW_LINE INDENT start , end = - 1 , - 1 NEW_LINE flag = True NEW_LINE i = 1 NEW_LINE while i < N : NEW_LINE INDENT if ( S [ i ] < S [ i - 1 ] ) : NEW_LINE INDENT if ( flag ) : NEW_LINE INDENT f , start , i , end = adjust ( S , i , start , end ) NEW_LINE if ( f == False ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE return NEW_LINE DEDENT flag = False NEW_LINE DEDENT else : NEW_LINE INDENT print ( - 1 ) NEW_LINE return NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT if ( start == - 1 ) : NEW_LINE INDENT start , end = 1 , 1 NEW_LINE DEDENT print ( start , end ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = " abcyxuz " NEW_LINE N = len ( S ) NEW_LINE isPossible ( S , N ) NEW_LINE DEDENT