SHERCHAL - Editorial

editorial
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

CAKEWALK

PREREQUISITES:

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