Divide given numeric string into at most two increasing subsequences which form an increasing string upon concatenation | Java program for the above approach ; Function to check for valid subsequences ; Stores which element belongs to which subsequence ; Check for each pos if a possible subsequence exist or not ; Last member of 1 subsequence ; Last Member of 2 nd subsequence ; Check if current element can go to 2 nd subsequence ; Check if the current elements belongs to first subsequence ; If the current element does not belong to any subsequence ; Check if last digit of first subsequence is greater than pos ; If a subsequence is found , find the subsequences ; Stores the resulting subsequences ; Print the subsequence ; If no subsequence found , print - 1 ; Driver Code
class GFG { static void findSubsequence ( String str ) { int n = str . length ( ) ; char [ ] res = new char [ n ] ; for ( int i = 0 ; i < n ; i ++ ) res [ i ] = 0 ; for ( int pos = 0 ; pos <= 9 ; pos ++ ) { char lst1 = '0' ; boolean flag = true ; char lst2 = ( char ) ( pos + '0' ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( lst2 <= str . charAt ( i ) ) { res [ i ] = '2' ; lst2 = str . charAt ( i ) ; } else if ( lst1 <= str . charAt ( i ) ) { res [ i ] = '1' ; lst1 = str . charAt ( i ) ; } else flag = false ; } if ( lst1 > pos + '0' ) flag = false ; if ( flag ) { String S1 = " " ; String S2 = " " ; for ( int i = 0 ; i < n ; i ++ ) { if ( res [ i ] == '1' ) { S1 += str . charAt ( i ) ; } else { S2 += str . charAt ( i ) ; } } System . out . print ( S1 + " ▁ " + S2 + "NEW_LINE"); return ; } } System . out . print ( " - 1" ) ; } public static void main ( String [ ] args ) { String S = "040425524644" ; findSubsequence ( S ) ; S = "123456789" ; findSubsequence ( S ) ; } }