PROBLEM LINK:Div2 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 atleast 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 pseudocode to illustrate this:
Time Complexity:$O(N.U)$, where $U$ = max length of input string. AUTHOR'S AND TESTER'S SOLUTIONS
This question is marked "community wiki".
asked 31 Mar '18, 19:16
