Question

Help Needed in Question | D.E shaw OA question | Set-8 | 2022

Answer 1

 

I had done the brute Force Approach. I know that, it gives TLE. Can anyone suggest how can we solve the problem in optmized way.

 

Here is my bruteForce solution:

 

int countBoxes(string digits, vector<string> passwords)
{
    int openBoxes = 0;
    bool flag = true;
    vector<int> digitsFreq(10), passwordFreq(10);
    for (auto &digit : digits)
        digitsFreq[digit - '0']++;
    for (auto &password : passwords)
    {
        for (auto &ch : password)
            passwordFreq[ch - '0']++;
        flag = true;
        for (int i = 0; i <= 9; i++)
        {
            if (digitsFreq[i] < passwordFreq[i])
                flag = false;
            passwordFreq[i] = 0;
        }
        if (flag)
            openBoxes++;
    }
    return openBoxes;
}

Answer 2

I think your approach is fine but you can optimize it by a quite a bit.

Use array, not vector. Vector is known to be slow.
Check the validity while you are going through each password, so we can stop early.

Maybe adding bit of filtering, eg. password.size() <= digits.size() etc could help filter out unnecessary computations
checking if passwordFreq[ch-'0'] > digitsFreq[ch-'0'] at every update, can also prevent further un required computations

Yes but it'll improve overall complexity
All the passwords whose length is more than digits can't be part of answer
At any point while processing, if frequency exceeds frequency in digits, its not an answers
Similarly other cases might be there, which will filter out unrequired processing for overall 100+ passwords

Your time complexity is n*length of passwords (102 * 10^5)
Filtering might leave only lets say 70 * 10^5 (and those 10^5 words might also get filter before processing the entire length, so maybe average processed length might fall below 10^5)