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