Divide given numeric string into at most two increasing subsequences which form an increasing string upon concatenation | 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
def findSubsequence ( str ) : NEW_LINE INDENT n = len ( str ) NEW_LINE res = [ '0' for i in range ( n ) ] NEW_LINE for pos in range ( 10 ) : NEW_LINE INDENT lst1 = '0' NEW_LINE flag = 1 NEW_LINE lst2 = chr ( pos + 48 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( lst2 <= str [ i ] ) : NEW_LINE INDENT res [ i ] = '2' NEW_LINE lst2 = str [ i ] NEW_LINE DEDENT elif ( lst1 <= str [ i ] ) : NEW_LINE INDENT res [ i ] = '1' NEW_LINE lst1 = str [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT flag = 0 NEW_LINE DEDENT DEDENT if ( lst1 > chr ( pos + 48 ) ) : NEW_LINE INDENT flag = 0 NEW_LINE DEDENT if ( flag ) : NEW_LINE INDENT S1 = " " NEW_LINE S2 = " " NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( res [ i ] == '1' ) : NEW_LINE INDENT S1 += str [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT S2 += str [ i ] NEW_LINE DEDENT DEDENT print ( S1 , S2 ) NEW_LINE return NEW_LINE DEDENT DEDENT print ( " - 1" ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = "040425524644" NEW_LINE findSubsequence ( S ) NEW_LINE S = "123456789" NEW_LINE findSubsequence ( S ) NEW_LINE DEDENT