# SHERCHAL - Editorial

Author: Sarvesh Kesharwani
Tester: Jay Sharma
Editorialist: Sarvesh Kesharwani

CAKEWALK

None

# PROBLEM:

Sherlock gives a challenge to Watson.

Sherlock gives Watson a string S. Watson has to find out the number of times he can spell “sherlock” using elements from the string S.

• The string S contains only lower-case characters.

Each character from the string S can be selected only once and the characters can be chosen in any order.

# EXPLANATION:

From the given string we have to calculate the frequencies of the letters of the word “sherlock”.
As we can make the word by rearranging the letters, we have to calculate the minimum frequency of the letters, that many times the word “sherlock” can be made.

# TIME COMPLEXITY:

O(N) per testcase.

# SOLUTIONS:

Setter's Solution
`````` #include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#define flash ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define ndl '\n'
#define mod 1000000007
void solve()
{
int tc;
cin >> tc;
while (tc--) {
int n;
string s;
cin >> n >> s;
string t = "sherlock";
map<char, int> mp;
for (char x : s) {
mp[x]++;
}
int ans = 100000;
for (char x : t) {
ans = min(ans, mp[x]);
}
cout << ans << '\n';
}
}
int main()
{
auto starttime = high_resolution_clock::now();
flash
solve();
auto endtime = high_resolution_clock::now();
double duration = duration_cast<microseconds>(endtime - starttime).count();
duration/=1000000;
cerr<<"Time Taken : "<<fixed<<setprecision(6)<<duration<<" secs"<<'\n';
return 0;
}
``````
Tester's Solution
``````/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/

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

int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt=1;
cin >> tt;
while(tt--)
{
int n;
cin >> n;
string s;
cin >> s;
string t = "sherlock";
int f[26];
for(int i=0;i<26;i++)
f[i]=0;
for(int i=0;i<n;i++)
f[s[i]-'a']++;
int ans = n;
for(int i=0;i<8;i++)
ans = min(ans,f[t[i]-'a']);
cout << ans << '\n';
}
return 0;
}
``````
Editorialist's Solution
``````#include<bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int tc;
cin >> tc;
while (tc--) {
int n;
string s;
cin >> n >> s;
string t = "sherlock";
map<char, int> mp;
for (char x : s) {
mp[x]++;
}
int ans = 100000;
for (char x : t) {
ans = min(ans, mp[x]);
}
cout << ans << '\n';
}
return 0;
}
``````
3 Likes