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

Easy

0/40

Average time to solve is 10m

Contributed by

4 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

3
codingninjas
sing
good human
14good
coder
code

Sample Output 1:

YES
NO
YES

Explanation of Input 1:

The first test case has already been explained in the problem statement.

For the second test case, STR1 = “good human” and STR2 = “14good”. We cannot form the second string using the characters of the first string. This is because “1” and “4” are not present in the string STR1.

For the third test case, STR1 = “coder” and STR2 = “code. We can form the second string using the characters of the first string. This is because “c”, “o”, “d”, “e” are present in the string STR1.

Sample Input 2:

3
madam
adam
H#LLO
hello
orange
orange

Sample Output 2

YES
NO
YES

Hint 1

Maintain count of characters.

Approaches (1)

Approach 1

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.

Time Complexity

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.

Space Complexity

O(1)

Since we are using a count array of constant size.

(100% EXP penalty)

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

Console