Check whether second string can be formed from characters of first string
You are given two strings STR1 and STR2. You need to check whether STR2 can be formed from the characters of STR1. Both the strings can contain any characters.

For example:

If STR1 = “codingninjas” and STR2 = “sing”. We can form the second string using the characters of the first string. This is because “s”, “i”, “n”, “g” are present in the string STR1.

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first line of each test case contains the first string STR1. The second line of each test case contains the second string STR2.

Output Format:

For each test case, return “YES” if the second string can be formed from the characters of the first string. Otherwise, return ”NO”. (without the inverted commas)

Note:

You are not required to print the expected output, and it has already been taken care of. Just implement the function.

Constraints:

1 ≤ T ≤ 100 1 ≤ |STR1|, |STR2| ≤ 1000 Where 'T' is the number of test cases, |STR1| and |STR2| are the lengths of the strings STR1 and STR2 respectively. Time Limit: 1 sec.

Question

Check whether second string can be formed from characters of first string

You are given two strings STR1 and STR2. You need to check whether STR2 can be formed from the characters of STR1. Both the strings can contain any characters.

For example:

If STR1 = “codingninjas” and STR2 = “sing”. We can form the second string using the characters of the first string. This is because “s”, “i”, “n”, “g” are present in the string STR1.

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 
Then the T test cases follow.
The first line of each test case contains the first string STR1.
The second line of each test case contains the second string STR2.

Output Format:

For each test case, return “YES” if the second string can be formed from the characters of the first string. Otherwise, return ”NO”. (without the inverted commas)

Note:

You are not required to print the expected output, and it has already been taken care of. Just implement the function.

Constraints:

1 ≤ T ≤ 100
1 ≤ |STR1|, |STR2| ≤ 1000

Where 'T' is the number of test cases, |STR1| and |STR2| are the lengths of the strings STR1 and STR2 respectively.
Time Limit: 1 sec.

Accepted Answer

Step 1 The idea was to count frequencies of string 1 and deduct from frequencies of string 2 simultaneously.
Step 2 If frequency at any stage becomes negative, false should be returned.

Accepted Answer

Using Counting Array

It can be seen from the problem that the order of the characters does not matter. Only the count of each character matters.
All the number of characters in STR2 should be present in STR1.
You need to maintain a count array/frequency array of size 256, which would store the frequency of each character in the given strings.
To do this, first traverse through the first string, STR1, and keep a count of the number of characters.
Now traverse through the second string, STR2, and keep subtracting the count of each character. If the count becomes negative at any point, that means the second string cannot be formed from characters of the first string, so return false, else return true.

Space Complexity: O(1)Explanation:

O(1)

Since we are using a count array of constant size.

Time Complexity: O(1)Explanation:

O(N + M), where ‘N’ is the length of the first string and ‘M’ is the length of the second string.

Since we are traversing through both the strings.