Check if given string can be formed by two other strings or their permutations | C ++ implementation of the approach ; Function to sort the given string using counting sort ; Array to store the count of each character ; Insert characters in the string in increasing order ; Function that returns true if str can be generated from any permutation of the two strings selected from the given vector ; Sort the given string ; Select two strings at a time from given vector ; Get the concatenated string ; Sort the resultant string ; If the resultant string is equal to the given string str ; No valid pair found ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  26 NEW_LINE void countingsort ( string & s ) { int count [ MAX ] = { 0 } ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { count [ s [ i ] - ' a ' ] ++ ; } int index = 0 ; for ( int i = 0 ; i < MAX ; i ++ ) { int j = 0 ; while ( j < count [ i ] ) { s [ index ++ ] = i + ' a ' ; j ++ ; } } } bool isPossible ( vector < string > v , string str ) { countingsort ( str ) ; for ( int i = 0 ; i < v . size ( ) - 1 ; i ++ ) { for ( int j = i + 1 ; j < v . size ( ) ; j ++ ) { string temp = v [ i ] + v [ j ] ; countingsort ( temp ) ; if ( temp . compare ( str ) == 0 ) { return true ; } } } return false ; } int main ( ) { string str = " amazon " ; vector < string > v { " fds " , " oxq " , " zoa " , " epw " , " amn " } ; if ( isPossible ( v , str ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }