Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Amazing Strings

Easy
0/40
Average time to solve is 15m
45 upvotes
Asked in companies
FlipkartUrban Company (UrbanClap)D.E.Shaw

Problem statement

Shrey has just arrived in the city. When he entered the city, he was given two strings. Now, after arriving at his college, his professor gave him an extra string. To check his intelligence, his professor told him to check if the third string given to him has all the characters of the first and second strings in any order. Help Shrey before his professor scolds him. He has to answer “YES” if all characters are present else “NO”.

Example: ‘HELLO’ and ‘SHREY’ are two initial strings, and his professor gave him ’HLOHEELSRY’. So, here all the characters are present, so he has to say “YES”.

Note: The strings contain only uppercase Latin characters.

Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case contains three strings, and the first two strings, i.e. ‘FIRST’ and ‘SECOND’ are the strings which he was given at the beginning, and the third string is ‘THIRD’, which was given by the professor.
Output Format:
For each test case, you have to return “YES” if all characters are present in the third string of the first and second strings; else, return “NO”.

 Print the output of each test case in a separate line.
Note:
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 10^2
1 <= |FIRST|, |SECOND|, |THIRD| <= 10^5

Time Limit: 1 sec
Sample Input 1:
2
HI HEY EIHYH
ALL GOOD ADOLLG
Sample Output 1:
YES
NO
Explanation For Sample Input 1:
In the first test case, the string ‘THIRD’ has all the characters present in the strings ‘FIRST’ and ‘SECOND’. So, we will return “YES”.

In the second test case, the strings ‘FIRST’ and ‘SECOND’ combined has 1 A, 2 L, 1 G, 2 O and 1 D. While the string ‘THIRD’ has 1 A, 2 L, 1 G, 1 O and 1 D and So, it has one character less than the combined ‘FIRST’ and ‘SECOND’. Thus, we will return “NO”.
Sample Input 1:
2
CODING NINJA NINCODINGJA
YES NO NEEOOYS
Sample Output 1:
YES
NO
Explanation For Sample Input 1:
In the first test case, the string ‘THIRD’ has all the characters present in the strings ‘FIRST’ and ‘SECOND’. So, we will return “YES”.

In the second test case, the strings ‘FIRST’ and ‘SECOND’ combined have 1 N, 1 Y, 1 E, 1 S and 1 O. While the string ‘THIRD’ has 1 N, 1 Y, 2 E, 1 S and 2 O and So, it has one character more than ‘FIRST’ and ‘SECOND’. Thus, we will return “NO”.
Hint

Can you think of iterating entirely in strings ‘FIRST’ and ‘SECOND’ and erasing the first occurrence of that character from ‘THIRD’?

Approaches (2)
Brute force

The basic idea of this approach is that we will initially iterate through both the strings (‘FIRST’ and ‘SECOND’) and for all the characters present in them we will try to remove the same character from ‘THIRD’. So, after every iteration, one character from string ‘THIRD’ will be removed and if the letter is not found in between then we will return “NO”. At last, we will check that if string ‘THIRD’ becomes empty that means that all characters match and will return “YES” or else will return “NO” as few extra characters are present in string ‘THIRD’.

 

Here is the algorithm:
 

  1. Declaring an array of size equal to length of the string ‘THIRD’ and assigning them value as 0.
  2. Iterating from starting of string ‘FIRST’ to ending of it.
    • Declare a temporary variable named ‘TEMP’ to keep track of the current character and initialize it with 0.
    • Check for the first occurrence of that particular character in the string ‘THIRD’.
      • If the character matches the current character of ‘FIRST’ and also the current character is not visited them we got the corresponding character for the current character.
        • Mark current index as visited and change of ‘TEMP’ variable to 1 as it indicates that corresponding character is found and break the loop.
    • If ‘TEMP’ is still 0 that means that the corresponding character is not found and so, return “NO”.
  3. Iterating from starting of string ‘SECOND’ to ending of it.
    • Declare a temporary variable named ‘TEMP’ to keep track of the current character and initialize it with 0.
    • Check for the first occurrence of that particular character in the string ‘THIRD’.
      • If the character matches the current character of ‘SECOND’ and also the current character is not visited them we got the corresponding character for the current character.
        • Mark current index as visited and change of ‘TEMP’ variable to 1 as it indicates that corresponding character is found and break the loop.
    • If ‘TEMP’ is still 0 that means that the corresponding character is not found and so, return “NO”.
  4. After iterating both the strings ‘FIRST’ and ‘SECOND’, we will check that if any character is still unvisited or not.
  5. If any character is found not visited then we will return “NO”, else “YES”.
Time Complexity

O(N^2), where N is the maximum length of the string from ‘FIRST’ and ‘SECOND’.
 

Because in the worst case we had to check for the occurrence of the character and that character is present at the end of the string in ‘THIRD’. So, we have to iterate through the entire string for all the characters. Thus, the time complexity is O(N^2).

Space Complexity

O(N), where N is the maximum length of the string from ‘FIRST’ and ‘SECOND’.
 

Because we are using any extra array for keeping track of the visited position of string ‘THIRD’.

Code Solution
(100% EXP penalty)
Amazing Strings
All tags
Sort by
Search icon

Interview problems

Easy python solution

def amazingStrings(first, second, third):

    new_s = first + second

 

    if len(new_s) != len(third):

        return "NO"

 

    s1 = {}

    s2 = {}  

    for ele in new_s:

        s1[ele] = s1.get(ele, 0) + 1

    

    for ele in third:

        s2[ele] = s2.get(ele, 0) + 1

    

    s1 = sorted(s1)

    s2 = sorted(s2)  

    if s1 != s2:

        return "NO"

    

    return "YES"

7 views
0 replies
0 upvotes

Interview problems

Easy approach, Beat 99%

string amazingStrings(string first, string second,string third) {

    // Write your code here.

 

    int cnt[26]={0};

    int cnt2[26]={0};

 

    for(char ch:first)

    {

        cnt[ch-'A']++;

    }

 

    for(char ch:second)

    {

        cnt[ch-'A']++;

    }

 

    for(char ch:third)

    {

        cnt2[ch-'A']++;

    }

 

    for(int i = 0; i<26; i++)

    {

        if(cnt[i]!=cnt2[i])

        return "NO";

    }

 

    return "YES";

}

 

278 views
0 replies
0 upvotes

Interview problems

O(n) | easy| no sorting| c++

#include<bits/stdc++.h>

using namespace std;

 

string amazingStrings(string first, string second,string third) {

    // Write your code here.

   vector<int>dp(256,0);

   for(auto i :third)

     dp[i]++;

   for(auto i: first)

    dp[i]--;

     for(auto i: second)

    dp[i]--;

 

    for(int i : dp)

    if(i!=0)

    return "NO";

    return "YES";

}

181 views
1 reply
1 upvote

Interview problems

C++ solution

#include <bits/stdc++.h>

string amazingStrings(string first, string second,string third) {
    // Write your code here.
    unordered_map<char,int>mp;

    for(int i=0;i<first.size();i++){
        mp[first[i]-'A']++;
    }
    for(int i=0;i<second.size();i++){
        mp[second[i]-'A']++;
    }

    for(int i=0;i<third.size();i++){
        mp[third[i]-'A']--;
    }

    for(auto it:mp){
        if(it.second<0 || it.second>0)
            return "NO";
    }
    return "YES";
 }
140 views
0 replies
1 upvote

Interview problems

Amazing Strings

string amazingStrings(string first, string second,string third) {
    // Write your code here.
    int str1[26] = {0};
    int str2[26] = {0};
    int str3[26] = {0};
    
    for(auto it : first){
        str1[it - 'A']++;
    }
    
    for(auto it : second){
        str2[it - 'A']++;
    }
    
    for(auto it : third){
        str3[it - 'A']++;
    }
    
    for(int i=0;i<26;i++){
        if(str1[i] + str2[i] != str3[i]) return "NO";
    }
    return "YES";
}

programming

datastructures

299 views
0 replies
1 upvote

Interview problems

C++ Solution - Beats 98% Submission - Easy to Understand

string amazingStrings(string first, string second,string third) {
    // Write your code here.int count[26] = {0};
    int count[26] = {0};
    for (int i = 0; i <  first.length(); i++){
        count[first[i] - 'A']++;
    }
     for (int i = 0;  i < second.length(); i++){
        count[second[i] - 'A']++;
     }
     for (int i = 0;  i < third.length(); i++){
        count[third[i] - 'A']++;
     }
    
    for (int i  = 0 ; i < 26; i++){
        if(count[i] % 2 != 0){
            return "NO";
        }
    }
    return "YES";
}
193 views
0 replies
1 upvote
profile

Interview problems

EASIEST ANSWER TO QUESTION | Cpp Solution |

string amazingStrings(string first, string second,string third) {
   // Write your code here.
   if((first.length() + second.length()) == third.length()){
       return "YES";
   }
   else{
       return "NO";
   }
}

Amazing Strings

270 views
1 reply
2 upvotes

Interview problems

Amazing Strings

#include<bits/stdc++.h>
string amazingStrings(string first, string second,string third) {
    // Write your code here.
    int f = first.size();
    int s = second.size();
    int t = third.size();
    if(f+s<t){
        return "NO";
    }else if(f+s>t){
        return "NO";
    }
    vector<int> v(26,0);
    int i=0;
    while(i<t){
        v[third[i]-65]++;
        i++;
    }
    i=0;
    while(i<f){
        if(v[first[i]-65]>0){
            v[first[i]-65]--;
            i++;
        }else{
            return "NO";
        }
    }
    i=0;
    while(i<s){
        if(v[second[i]-65]>0){
            v[second[i]-65]--;
            i++;
        }else{
            return "NO";
        }
    }
    return "YES";
    /*
    unordered_map<char,int> m;
    for(char ch:third){
        m[ch]++;
    }
    
    int i=0;int j=0;
    while(i<f && j<s){
        if(m[first[i]]>0){
            m[first[i]]--;
            i++;
        }else{
            return "NO";
        }
        if(m[second[j]]>0){
            m[second[j]]--;
            j++;
        }else{
            return "NO";
        }
    }
    while(i<f){
        if(m[first[i]]>0){
            m[first[i]]--;
            i++;
        }else{
            return "NO";
        }
    }
    while(j<s){
        if(m[second[j]]>0){
            m[second[j]]--;
            j++;
        }else{
            return "NO";
        }
    }
    return "YES";
    */
        /*
 for(int i=0;i<first.size();i++){
        if(m[first[i]]>0){
            m[first[i]]--;
        }else{
            return "NO";
        }
    }
    for(int i=0;i<second.size();i++){
        if(m[second[i]]>0){
            m[second[i]]--;
        }else{
            return "NO";
        }
    }
    return "YES";
    */
}

Amazing Strings

194 views
0 replies
0 upvotes

Interview problems

Discussion thread on Interview Problem | Amazing Strings

Hey everyone, creating this thread to discuss the interview problem - Amazing Strings.

 

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Amazing Strings

 

181 views
1 reply
0 upvotes
Full screen
Console