Noogler_from_Google's blog

By Noogler_from_Google, history, 5 weeks ago, In English

Not able to think any solution in given Constraint. If anyone saw a similar question then please comment the link to that.

You are provided with a large string and one or more small strings. You need to find if the large string can be formed by combining all the small strings. You can interchange characters of small strings internally and you can combine small strings in any order. Print "YES" if it is possible, otherwise print "NO".

Note: All strings contain lower case alphabets only.

Constraints
1 <= length of large string <= 500000
1 <= length of small string <= 1000
1 <= N <= 500

Input
First line contains the large string
Second line contains an integer N denoting total number of small strings
Next N lines contain strings smaller than large string

Output
Print single line with YES or NO

Time Limit
1

Examples
Example 1

Input

dogisaloyalanimal
5
a
alloy
is
god
lamina

Output
YES

Explanation :

Large string is "dogisaloyalanimal". There are 5 small strings — "a", "alloy", "is", "god", "lamina". We can do following operations on small strings:
Interchange characters of "alloy" to form "loyal".
Interchange characters of "god" to form "dog".
Interchange characters of "lamina" to form "animal".
So, we formed new set of small strings — "a", "loyal", "is", "dog", "animal". Now combine small strings in the below order:
"dog" + "is" + "a" + "loyal" + "animal"
We got it combined as "dogisaloyalanimal". This is same as large string provided. So, the output is "YES".

Example 2

Input

thisisgood
4
god
is
so
hit

Output
NO

Explanation:

Large string is "thisisgood". There are 4 small strings — "god", "is", "so", "hit". We cannot form the large string by combining small strings even after interchanging its characters internally. So, the output is "NO".

 
 
 
 
  • Vote: I like it
  • -34
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the way to solve this problem is similar to word break problem which needs trie and dp to make it n^2 . only thing to keep in mind is we can store strings in trie in sorted manner. if we want to find any substring is present in the trie or not , then we can simply sort the substring and find its occurence in trie. the complexity would be n^3 in this case.

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

The problem is from an ongoing challenge named Codevita.