Number of Strings That Appear as Substrings in Word

Number of Strings That Appear as Substrings in Word

What is this problem about?

The Number of Strings That Appear as Substrings in Word problem gives you a list of patterns and a target string word. Count how many patterns from the list appear as substrings in word. This easy coding problem tests straightforward substring containment checking.

Why is this asked in interviews?

Uber asks this easy problem as a quick screening to verify Python/Java/C++ substring operations and basic iteration. It tests whether candidates use built-in in operator (Python) or contains/indexOf methods cleanly. The array and string interview pattern is demonstrated at its simplest.

Algorithmic pattern used

Linear scan with substring check. For each pattern p in patterns, check if p is a substring of word using p in word (Python) or word.contains(p) (Java). Count True results.

Example explanation

patterns=["a","abc","bc","d"], word="abc".

• "a" in "abc" ✓.
• "abc" in "abc" ✓.
• "bc" in "abc" ✓.
• "d" in "abc" ✗. Count = 3.

Common mistakes candidates make

• Implementing substring search manually with nested loops when built-ins work.
• Checking if pattern equals word instead of if pattern is a substring.
• Using regex when simple containment check suffices.
• Not handling empty pattern strings (empty string is substring of everything).

Interview preparation tip

Easy problems test implementation speed and familiarity with standard library functions. Know your language's substring check: Python s in t, Java t.contains(s), C++ t.find(s) != string::npos. For interviews, using the most readable, correct built-in demonstrates language mastery. If the interviewer asks for a custom implementation, describe KMP or Rabin-Karp as efficient alternatives without building them for this trivially-sized problem.