FRK - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Div2

Practice

Author: Misha Chorniy

Tester: Lewin Gan

Editorialist: Adarsh Kumar

DIFFICULTY:

Easy

PREREQUISITES:

Familiarity with 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 \ge 2 with the string “chef”.

EXPLANATION:

For an input string and word “chef” to have a common substring of length \ge 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 element from the input string is one from the above set. A pseudo-code to illustrate this:

def solve(N):
  ANS=0
  for i = 1...N:
    u = input[i]  # assume input[i] to be the ith string input
    l = len(u)   
    for j = 0...l-2:  # assume u to be in 0-based indexing
      if (u[j]=='c' && u[j+1]=='h')||(u[j]=='h' && u[j+1]=='e')||(u[j]=='e' && u[j+1]=='f'):
        ANS+=1
        break
  return ANS

Time Complexity:

O(N.U), where U = max length of input string.

AUTHOR’S AND TESTER’S SOLUTIONS

Setter’s solution

Tester’s solution

2

t=int(input())
n=0
while t:
t=t-1
a=input()

m=len(a)

for i in range(1,m-1):
    if a[i]=='h':
        if a[i-1]=='c' or (i+1<m and a[i+1])=='e':
            n=n+1
            break
    elif a[i-1]=='e' and a[i]=='f':
        n=n+1
        break

print(n)

please tell me whats wrong with tthis???..