Number of Strings That Appear as Substrings in Word Python/Java solution

In Python, iterate through patterns and check 'if pattern in word'. In Java, use word.contains(pattern). Both implementations follow the same logic: scan each pattern and increment a counter when it appears as a substring. The complexity remains O(p * n).

How to solve Number of Strings That Appear as Substrings in Word in O(n)?

A strict O(n) solution is not necessary for this problem because the constraints are small. The common solution checks each pattern separately against the word using substring search, leading to O(p * n) time. More advanced string algorithms like Aho–Corasick could reduce repeated scans, but they are unnecessary for typical interview constraints.

What is the best approach for Number of Strings That Appear as Substrings in Word?

The best approach is a direct substring check for each pattern. Iterate through the patterns array and use a built-in function such as contains(), indexOf(), or the Python 'in' operator to check if the pattern exists in the word. This keeps the implementation simple and runs in O(p * n) time where p is the number of patterns and n is the length of the word.

Is Number of Strings That Appear as Substrings in Word asked at Google/Amazon/Meta?

This problem is categorized as Easy and commonly appears in coding practice platforms to test basic string manipulation and array iteration. Variants of substring matching frequently appear in interviews at companies like Amazon, Google, and Meta, especially as warm-up questions before harder string problems.

What data structure is used in Number of Strings That Appear as Substrings in Word?

The problem primarily uses arrays and strings. You iterate through the patterns array and perform substring checks on the word string. No advanced data structures are required for the standard solution.

What is the time complexity of Number of Strings That Appear as Substrings in Word?

The typical solution runs in O(p * n) time. You check each of the p patterns against the target word of length n using a substring search. Space complexity is O(1) because the algorithm only keeps a counter and does not allocate additional data structures proportional to input size.

Description Hints 2 Solution Video 4:34

1967. Number of Strings That Appear as Substrings in Word

Q: Is Number of Strings That Appear as Substrings in Word easy or hard?

The problem is rated Easy with a high acceptance rate around 80%+. It mainly tests understanding of substring search and simple iteration over arrays, making it a common beginner-friendly string problem.

Easy86.1% acceptance6 companies

Given an array of strings patterns and a string word, return the number of strings in patterns that exist as a substring in word.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: patterns = ["a","abc","bc","d"], word = "abc"
Output: 3
Explanation:
- "a" appears as a substring in "abc".
- "abc" appears as a substring in "abc".
- "bc" appears as a substring in "abc".
- "d" does not appear as a substring in "abc".
3 of the strings in patterns appear as a substring in word.

Example 2:

Input: patterns = ["a","b","c"], word = "aaaaabbbbb"
Output: 2
Explanation:
- "a" appears as a substring in "aaaaabbbbb".
- "b" appears as a substring in "aaaaabbbbb".
- "c" does not appear as a substring in "aaaaabbbbb".
2 of the strings in patterns appear as a substring in word.

Example 3:

Input: patterns = ["a","a","a"], word = "ab"
Output: 3
Explanation: Each of the patterns appears as a substring in word "ab".

Constraints:

1 <= patterns.length <= 100
1 <= patterns[i].length <= 100
1 <= word.length <= 100
patterns[i] and word consist of lowercase English letters.

Asked at 6 companies

Meta Uber

Google Amazon Microsoft Bloomberg

Topics

Array String

Hints open one at a time

Hint 1

Deal with each of the patterns individually.

Hint 2

Use the built-in function in the language you are using to find if the pattern exists as a substring in word.

4:34

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def numOfStrings(self, patterns: List[str], word: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

["a","abc","bc","d"]
"abc"

Input

["a","b","c"]
"aaaaabbbbb"

Input

["a","a","a"]
"ab"

Your code is saved on this device.Solution