Number of Strings That Appear as Substrings in Word

LeetCode 1967, Number of Strings That Appear as Substrings in Word, gives you an array of strings patterns and a string word. Return the number of strings in patterns that exist as a substring in word.

A string a is a substring of string b if a can be found as a contiguous sequence of characters somewhere inside b.

Examples:

• patterns = ["a", "abc", "bc", "d"], word = "abc" returns 3 (because "a", "abc", and "bc" are all substrings of "abc", but "d" is not)
• patterns = ["a", "b", "c"], word = "aaaaabbbbb" returns 2 (because "a" and "b" are substrings, but "c" is not)

The approach: check each pattern

This problem asks one question per pattern: "Is this pattern a substring of word?" You just need to iterate through the patterns array and check each one.

In Python, the in operator handles substring checks directly. The expression pattern in word returns True if pattern appears anywhere inside word as a contiguous sequence. You count up the number of patterns where this check passes.

There is no need for a sliding window, two pointers, or any advanced string matching algorithm. The problem is a direct loop over the patterns with a built-in substring test.

The code

def num_of_strings(patterns, word):
    count = 0
    for p in patterns:
        if p in word:
            count += 1
    return count

You can also write this as a one-liner using sum with a generator expression:

def num_of_strings(patterns, word):
    return sum(1 for p in patterns if p in word)

Both versions do the same thing. The explicit loop is clearer for understanding the logic. The one-liner is idiomatic Python.

Visual walkthrough

Let's trace through patterns = ["a", "abc", "bc", "d"] with word = "abc", checking each pattern one by one.

Three of the four patterns were found inside the word. The algorithm checks each pattern independently and counts the matches. The final answer is 3.

Complexity analysis

For each of the n patterns, the substring check scans through word comparing up to m characters at each position. In the worst case, this means k - m + 1 starting positions, each comparing m characters.

Given the problem's constraints (both patterns and word have lengths up to 100), this runs in constant time in practice. The brute-force approach is perfectly efficient here.

Building blocks

This problem uses one fundamental technique that appears across many string problems.

Substring check

The core operation is determining whether one string appears inside another. In Python, p in word handles this. Under the hood, this is the same operation used in problems like finding the first occurrence of a needle in a haystack. The difference here is that you do not need the index of the match, just whether a match exists.

Linear scan with a counter

The outer structure is a simple pattern: iterate through a collection, test a condition on each element, and count how many pass. This "filter and count" template appears in problems ranging from counting valid parentheses to filtering arrays by some property. Recognizing this template lets you focus on the interesting part of each problem (the condition being tested) rather than the boilerplate around it.

Edge cases

Pattern equals word. If a pattern is identical to word, it is a substring (every string is a substring of itself). The in operator returns True for this case.

Pattern longer than word. If a pattern has more characters than word, it cannot be a substring. The in operator returns False, so no special handling is needed.

Duplicate patterns. If the same string appears multiple times in patterns, each occurrence is counted independently. For example, patterns = ["a", "a"] with word = "a" returns 2, not 1. The problem asks you to count how many strings in the array are substrings, not how many distinct substrings.

Empty pattern. An empty string is technically a substring of any string. The constraints guarantee patterns have at least length 1, but if you wanted to handle it, "" in word returns True in Python.

Single character patterns. Each single character pattern is checked against word individually. If word = "abc" and patterns = ["a", "b", "c", "d"], you get 3 because "a", "b", and "c" each appear in word.

From understanding to recall

This problem feels almost too simple when you read the solution. Loop through patterns, check in, count matches. But the building blocks here, substring checking and the filter-count pattern, show up in many harder problems. When you encounter a problem like "count how many words from a dictionary appear in a sentence" or "filter patterns that match a target," you want these templates to fire automatically.

Spaced repetition helps you lock in the pattern so it becomes second nature. You practice writing the loop, the condition, and the count from scratch at increasing intervals. After a few reps, the structure is in your fingers, and you can focus your energy on the harder parts of more complex problems.

Related posts

• Find the Index of the First Occurrence in a String - A related substring problem where you need to find the position of a match, not just whether one exists
• Longest Common Prefix - Another easy string problem that involves comparing characters across multiple strings
• Valid Anagram - A string problem that uses frequency counting to compare string composition