# PROBLEM LINK:

**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;
}
```