Links:

• Contest Link
• Problem Link

Author and Tester: vedang12d

Editorialist: MPatil123

Difficulty:

Medium

Problem:

Neytiri wants to create multiple copies of target word. Since there are no printers on Pandora, they use cutouts of characters available with them to create copies.

You have to help her find out the maximum number of copies of the target word she can create by rearranging characters that are available with her.

Formally, You are given a string S, where each character is a small english alphabets. Output how many maximum copies of target string T you can create using character from string S.

Note: You can use one character from string S not more than once.

Input Format:

• The first line contains a string S, cutouts of characters available with Neytiri.
• The second line contains a string T which denotes the target word.

Constraints:

• 1 ≤ |S| , |T| ≤ 10⁶ where |S| denotes the length of S.
• S and T contain lowercase characters.

Output Format:

Output the maximum number of target words that can be formed using cutouts of characters available with Neytiri.

Explanation:

In this question we have to find out minimum number of times the target word (string T) can be formed with the help of other set of given characters (string S). So in order to find that we have to store the count of all the different characters in both the strings. This can be done by declaring two vectors of size 26 and storing count of characters in respective vectors.

Once the count is stored find the character in string T which is also present in string S with minimum number of count for each occurrence out of all characters in string S. Since the characters can be repeated in string T divide the number of occurrences of the given character in string S by the number of occurrences of given character in string T. Find the minimum of all answers obtained in these operations.

Note: Maps can also be used as an alternative to store the count of the characters in the strings.

Code:

#include <bits/stdc++.h>
using namespace std;

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    
    string t,s;
    cin>>s>>t;
    
    vector<int> sc(26,0);
    vector<int> tc(26,0);
    
    for(int i=0;i<s.size();i++)
        sc[s[i]-'a']++;
    for(int i=0;i<t.size();i++)
        tc[t[i]-'a']++;
    
    int mn=INT_MAX;
    for(int i=0;i<26;i++)
    {
        if(tc[i]!=0)
        mn=min(mn,sc[i]/tc[i]);
    }
    cout<<mn<<"\n";
    return 0;
}

Time Complexity:

Time Complexity for the problem is O(|S|+|T|) where |S| and |T| are the lengths of string S and T respectively.