Rearrange a string S1 such that another given string S2 is not its subsequence | Function to rearrange characters in S1 such that S2 is not a subsequence of it ; Store the frequencies of characters of s2 ; Traverse the s2 ; Update the frequency ; Find the number of unique characters in s2 ; Increment unique by 1 if the condition satisfies ; Check if the number of unique characters in s2 is 1 ; Store the unique character frequency ; Store occurence of it in s1 ; Find count of that character in the s1 ; Increment count by 1 if that unique character is same as current character ; If count count_in_s1 is less than count_in_s2 , then prs1 and return ; Otherwise , there is no possible arrangement ; Checks if any character in s2 is less than its next character ; Iterate the string , s2 ; If s [ i ] is greater than the s [ i + 1 ] ; Set inc to 0 ; If inc = 1 , prs1 in decreasing order ; Otherwise , prs1 in increasing order ; Driver code
def rearrangeString ( s1 , s2 ) : NEW_LINE INDENT cnt = [ 0 ] * 26 NEW_LINE for i in range ( len ( s2 ) ) : NEW_LINE INDENT cnt [ ord ( s2 [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT unique = 0 NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT if ( cnt [ i ] != 0 ) : NEW_LINE INDENT unique += 1 NEW_LINE DEDENT DEDENT if ( unique == 1 ) : NEW_LINE INDENT count_in_s2 = len ( s2 ) NEW_LINE count_in_s1 = 0 NEW_LINE for i in range ( len ( s1 ) ) : NEW_LINE INDENT if ( s1 [ i ] == s2 [ 0 ] ) : NEW_LINE INDENT count_in_s1 += 1 NEW_LINE DEDENT DEDENT if ( count_in_s1 < count_in_s2 ) : NEW_LINE INDENT print ( s1 , end = " " ) NEW_LINE return NEW_LINE DEDENT print ( - 1 , end = " " ) NEW_LINE DEDENT else : NEW_LINE INDENT inc = 1 NEW_LINE for i in range ( len ( s2 ) - 1 ) : NEW_LINE INDENT if ( s2 [ i ] > s2 [ i + 1 ] ) : NEW_LINE INDENT inc = 0 NEW_LINE DEDENT DEDENT if ( inc == 1 ) : NEW_LINE INDENT s1 = sorted ( s1 ) [ : : - 1 ] NEW_LINE print ( " " . join ( s1 ) , end = " " ) NEW_LINE DEDENT else : NEW_LINE INDENT s1 = sorted ( s1 ) NEW_LINE print ( " " . join ( s1 ) , end = " " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s1 , s2 = " abcd " , " ab " NEW_LINE rearrangeString ( s1 , s2 ) NEW_LINE DEDENT