×

# FRK - Editorial

Div2
Practice

Author: Misha Chorniy
Tester: Lewin Gan

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

This question is marked "community wiki".

306719
accept rate: 7%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,719
×3,770
×644
×47
×3

question asked: 31 Mar '18, 19:16

question was seen: 357 times

last updated: 01 Apr '18, 23:36