MUDAS - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest

Setter: Nihal Mittal

Editorialist: Nihal Mittal

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic observations

PROBLEM:

Given a string S, determine the minimum number of operations to apply so that the string contains atleast one substring as “Muda”.

EXPLANATION

The string “Muda” contains only 4 characters so the maximum number of operations one can perform is 4. So we iterate on the given string and if we are on a position i then we check whether position i , i+1, i+2, i+3 contains the characters “M”, “u”, “d”, “a” respectively. Then we choose such substring such that cnt is maximised where cnt is the maximum number of characters that belong to the string “Muda” in a substring of s.
Then the answer is 4 - max(cnt(s[i...i+3])) for all 1<=i<=|S|-3 .

TIME COMPLEXITY

Time complexity is O(|S|) per test case.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int cn = 0,i;
        string s;
        cin>>s;
        for(i=0;i<s.length()-3;i++)
        {
            int tc = 0;
            if(s[i]=='M') tc++;
            if(s[i+1]=='u') tc++;
            if(s[i+2]=='d') tc++;
            if(s[i+3]=='a') tc++;
            cn = max(cn,tc);
        }
        cout<<4-cn<<"\n";
    }
return 0;
}
1 Like
2

If in this problem we would have to find an unknown string which could only be known at runtime(would be scanned by program) then would it’s time complexity be
O(n* n *s) where n is size of string to be found and s is size of string in which we have to find other string
is it possible to reduce complexity of such problem?

3

Hi, This complexity can be improved to O(n * s) by using sliding window technique and maintaining a deque of characters and the size of deque would be n.

1 Like
4

I don’t know whether this is one the ways, but the first thing that struck me was this.
My solution

5

Yes this is a also a valid way to solve the problem.