Rearrange a string S1 such that another given string S2 is not its subsequence | C ++ program for the above approach ; Function to rearrange characters in string S1 such that S2 is not a subsequence of it ; Store the frequencies of characters of string s2 ; Traverse the string 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 string s2 is 1 ; Store the unique character frequency ; Store occurence of it in s1 ; Find count of that character in the string 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 print s1 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 , print s1 in decreasing order ; Otherwise , print s1 in increasing order ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void rearrangeString ( string s1 , string s2 ) { int cnt [ 26 ] = { 0 } ; for ( int i = 0 ; i < s2 . size ( ) ; i ++ ) cnt [ s2 [ i ] - ' a ' ] ++ ; int unique = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) if ( cnt [ i ] != 0 ) unique ++ ; if ( unique == 1 ) { int count_in_s2 = s2 . size ( ) ; int count_in_s1 = 0 ; for ( int i = 0 ; i < s1 . size ( ) ; i ++ ) if ( s1 [ i ] == s2 [ 0 ] ) count_in_s1 ++ ; if ( count_in_s1 < count_in_s2 ) { cout << s1 ; return ; } cout << -1 ; } else { int inc = 1 ; for ( int i = 0 ; i < s2 . size ( ) - 1 ; i ++ ) if ( s2 [ i ] > s2 [ i + 1 ] ) inc = 0 ; if ( inc == 1 ) { sort ( s1 . begin ( ) , s1 . end ( ) , greater < char > ( ) ) ; cout << s1 ; } else { sort ( s1 . begin ( ) , s1 . end ( ) ) ; cout << s1 ; } } } int main ( ) { string s1 = " abcd " , s2 = " ab " ; rearrangeString ( s1 , s2 ) ; return 0 ; }