BJAGGU - Bheem and Jaggu

editorial
, , ,
1

Problem Link : CodeChef: Practical coding for everyone

Initially we are given n strings. We have to find the minimum number of strings from which the characters of given string can be extracted.

We will store the frequency of every character in every string and then start from every string and check how many strings are needed so that this new string is the subsequence of those strings.

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


int arr[10005][26];


int main()
{
    int n;
    cin >> n;
    int m;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        m = s.size();
        for (int j = 0; j < m; j++)
        {
            arr[i][s[j] - 97]++;
        }
    }
    int q;
    cin >> q;
    while (q--)
    {
        string s;
        cin >> s;
        int alpha[26] = {0};
        m = s.size();
        for (int i = 0; i < m; i++)
        {
            alpha[s[i] - 97]++;
        }
        int ans = INT_MAX;
        int i = 0, j = -1;
        int cur[26] = {0};
        while (i < n && j < n)
        {
            bool check = 0;
            for (int k = 0; k < 26; k++)
            {
                if (cur[k] < alpha[k])
                {
                    check = 1;
                }
            }
            if (check)
            {
                j++;
                for (int k = 0; k < 26; k++)
                {
                    cur[k] += arr[j][k];
                }
            }
            else
            {
                ans = min(ans, j - i + 1);
                for (int k = 0; k < 26; k++)
                {
                    cur[k] -= arr[i][k];
                }
                i++;
            }
        }
        if (ans == INT_MAX)
            cout << -1 << endl;
        else
            cout << ans << endl;
    }
    return 0;
}
1 Like