CKS002 - Editorial

Mahabali Bheem and The Chef

Author: artha6391
Tester: anushka_nagar
Editorialist: chetna791

DIFFICULTY:

EASY

PREREQUISITES:

Understanding of Strings

PROBLEM:

You are given list of N strings. You need to count number of strings in the given list, that have a common substring of length \geq 2 with the string “chef”.

QUICK EXPLANATION:

For an input string and word “chef” to have a common substring of length \geq 2, input string must contain at least one of the strings from following set as substring {“ch”,“he”,“ef”,“che”,“hef”,“chef”}. The set is redundant and can be reduced to {“ch”,“he”,“ef”} (Why?). Hence, you only need to check if two consecutive elements from the input string is one from the above set.

SOLUTIONS:

Setter’s Solution

#include <bits/stdc++.h>
using namespace std;
const int MaxN = (int)1e6 + 10;
const int INF = 1e9;
int main()
{
int n;
cin >> n;
int cnt = 0;
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
bool ok = false;
for (int j = 0; j + 1 < (int)s.length(); ++j) {
if (s[j] == ‘c’ && s[j + 1] == ‘h’ ||
s[j] == ‘h’ && s[j + 1] == ‘e’ ||
s[j] == ‘e’ && s[j + 1] == ‘f’) {
ok = true;
}
}
cnt += ok;
}
cout << cnt << ‘\n’;
return 0;
}

Tester’s Solution

#include <bits/stdc++.h>
using namespace std;
const int MaxN = (int)1e6 + 10;
const int INF = 1e9;
int main()
{
int n;
cin >> n;
int cnt = 0;
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
bool ok = false;
for (int j = 0; j + 1 < (int)s.length(); ++j) {
if (s[j] == ‘c’ && s[j + 1] == ‘h’ ||
s[j] == ‘h’ && s[j + 1] == ‘e’ ||
s[j] == ‘e’ && s[j + 1] == ‘f’) {
ok = true;
}
}
cnt += ok;
}
cout << cnt << ‘\n’;
return 0;
}

Editorialist’s Solution

#include <bits/stdc++.h>
using namespace std;
const int MaxN = (int)1e6 + 10;
const int INF = 1e9;
int main()
{
int n;
cin >> n;
int cnt = 0;
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
bool ok = false;
for (int j = 0; j + 1 < (int)s.length(); ++j) {
if (s[j] == ‘c’ && s[j + 1] == ‘h’ ||
s[j] == ‘h’ && s[j + 1] == ‘e’ ||
s[j] == ‘e’ && s[j + 1] == ‘f’) {
ok = true;
}
}
cnt += ok;
}
cout << cnt << ‘\n’;
return 0;
}