Number of Strings That Appear as Substrings in Word - Solution & Explanation

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.

Q: 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).

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

EasyArray String10 min readAsked at: Amazon, Microsoft, Meta +3

Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given an array patterns and a string word. The task is to count how many strings in patterns appear as a substring inside word. Each pattern is checked independently, and duplicates in the array are counted separately if they match.

This problem is mainly about efficient substring detection using basic string operations. Since the constraints are small, a direct check works well and keeps the implementation clean.

Approach 1: Simple String Contains Check (O(p * n) time, O(1) space)

The most straightforward solution iterates through every string in patterns and checks whether it appears inside word. Most languages provide a built-in substring search such as word.contains(pattern), pattern in word, or indexOf(). Each check scans the target string and determines whether the pattern exists.

The algorithm is simple: iterate over the array of patterns, perform a substring search against word, and increment a counter when a match is found. If there are p patterns and the length of word is n, each search costs up to O(n), resulting in O(p * n) total time. Space usage stays O(1) since no additional data structures are required.

This approach is usually the best choice. Built‑in string search functions are highly optimized and the implementation takes only a few lines.

Approach 2: Pattern Matching with Regular Expressions (O(p * n) time, O(1) space)

Another option uses regular expressions to check if each pattern occurs inside the word. For each string in patterns, compile or construct a regex pattern and test it against word. If the expression matches, the pattern exists as a substring.

The core logic is similar to the previous approach but relies on regex engines for pattern matching. This can be useful in languages like Python or JavaScript where regex matching is concise. However, regex introduces additional overhead and offers no real advantage for simple substring checks.

Time complexity remains O(p * n) because each regex evaluation scans the word. Space complexity stays O(1) since no extra storage proportional to input size is needed.

Recommended for interviews: The simple substring check is what most interviewers expect. It shows you understand how to iterate through the input and leverage efficient built-in string operations. Regex works but is rarely necessary for this problem and can appear overengineered for an Easy-level task.

Approach 1: Using Simple String Contains Check

This approach involves iterating through each string in the 'patterns' array and checking if it appears as a substring in the given 'word'. A substring can be detected using available functions that check whether one string is a substring of another, such as contains() methods in various languages.

The main function takes an array of string patterns and a word. Using the strstr() function in C, it iterates over each pattern to check if it's a substring of the word, incrementing the count if true.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n*m) where n is the number of patterns and m is the average length of the patterns.
Space Complexity: O(1) as we are using a constant amount of extra space.

Try this approach in the editor →

Approach 2: Using Pattern Matching with Regular Expressions

Another approach to solve this problem is to utilize regular expressions for pattern matching. For each string in the 'patterns' array, create a regular expression and test if it matches a substring in 'word'. Though this approach might be overkill for simpler patterns, it demonstrates an alternative use of pattern matching.

In this Python solution, the re.search() method is used to search for each pattern in 'word'. re.search() returns a match object if a pattern is found, and None otherwise.

Code

Python JavaScript

Python

JavaScript

Complexity

Time Complexity: O(n*m) where n is the number of patterns and m is the average length of the patterns.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Simulation

Traverse each string p in the array patterns and check if it is a substring of word. If it is, increment the answer by one.

After traversing, return the answer.

The time complexity is O(n times m), and the space complexity is O(1). Here, n and m are the lengths of patterns and word, respectively.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Using Simple String Contains Check	Time Complexity: O(n*m) where n is the number of patterns and m is the average length of the patterns. Space Complexity: O(1) as we are using a constant amount of extra space.
Using Pattern Matching with Regular Expressions	Time Complexity: O(n*m) where n is the number of patterns and m is the average length of the patterns. Space Complexity: O(1).
Simulation	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Simple String Contains Check	O(p * n)	O(1)	Best general solution. Clean, readable, and uses optimized built-in substring search.
Pattern Matching with Regular Expressions	O(p * n)	O(1)	Useful if regex is already part of the workflow or when more complex matching rules are needed.

Video Solution

Number of Strings That Appear as Substrings in Word 🔥 Leetcode 1967 | String Problem Explained • Study Placement • 867 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

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.

Ready to solve this problem?

Practice Number of Strings That Appear as Substrings in Word with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyEasy

Acceptance86.1%

Approaches3

Reading time10 min

Asked at

Amazon Microsoft Meta Uber Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Using Simple String Contains Check

Code

Complexity

Approach 2: Using Pattern Matching with Regular Expressions

Code

Complexity

Approach 3: Simulation

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents