Number of Strings That Appear as Substrings in Word solution and explanation
Google
9 more videos on this problem
Number of Strings That Appear as Substrings in Word 🔥 Leetcode 1967 | String Problem Explained Study Placement · 4:34 · 867 views
1967. Number of Strings That Appear as Substrings in Word (Leetcode Easy)Programming Live with Larry · 3:20 · 568 views
1967. Number of Strings That Appear as Substrings in Word | Leetcode Daily - PythonLeetcode Daily · 5:37 · 298 views
Number of Strings That Appear as Substrings in Word - LeetCode 1967 - Javaalgobest - Computer Science · 3:49 · 266 views
1967. Number of Strings That Appear as Substrings in Word || using python3 ||Leetcodeseries solutionOmnyEvolutions · 3:09 · 258 views
1967. Number of Strings That Appear as Substrings in Word | POTD 29 June 2026 | C++ | LeetcodeTechie On Track · 5:53 · 242 views
Number of Strings That Appear as Substrings in Word | LeetCode 1967 - Pythonimpoldev · 5:08 · 229 views
Number of Strings That Appear as Substrings in Word | LeetCode 1967 | Java Code | Developer CoderDeveloper Coder · 2:53 · 140 views
Daily Leetcode #2281: Jun 29, 2026 - 1967. Number of Strings That Appear as Substrings in WordProgramming Live with Larry · 2:19 · 139 views
1967. Number of Strings That Appear as Substrings in Word with python | Leetcode with pythonArsalan Ahmed · 3:38 · 95 views
The problem
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 <= 1001 <= patterns[i].length <= 1001 <= word.length <= 100patterns[i]andwordconsist 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.
def count_substrings(word, patterns):
count = 0
for pattern in patterns:
if pattern in word:
count += 1
return count
patterns = ["a", "b", "c"]
word = "aaaaabbbbb"
print(count_substrings(word, patterns))import java.util.List;
public class SubstringCounter {
public static int countSubstrings(String word, List<String> patterns) {
int count = 0;
for (String pattern : patterns) {
if (word.contains(pattern)) {
count++;
}
}
return count;
}
public static void main(String[] args) {
List<String> patterns = List.of("a", "b", "c");
String word = "aaaaabbbbb";
System.out.println(countSubstrings(word, patterns));
}
}#include <iostream>
#include <vector>
using namespace std;
int countSubstrings(const string &word, const vector<string> &patterns) {
int count = 0;
for (const auto &pattern : patterns) {
if (word.find(pattern) != string::npos) {
count++;
}
}
return count;
}
int main() {
vector<string> patterns = {"a", "b", "c"};
string word = "aaaaabbbbb";
cout << countSubstrings(word, patterns) << endl;
return 0;
}function countSubstrings(word, patterns) {
let count = 0;
patterns.forEach(pattern => {
if (word.includes(pattern)) {
count++;
}
});
return count;
}
const patterns = ["a", "b", "c"];
const word = "aaaaabbbbb";
console.log(countSubstrings(word, patterns));#include <stdio.h>
#include <string.h>
int countSubstrings(char *word, char *patterns[], int size) {
int count = 0;
for (int i = 0; i < size; i++) {
if (strstr(word, patterns[i])) {
count++;
}
}
return count;
}
int main() {
char *patterns[] = {"a", "b", "c"};
char word[] = "aaaaabbbbb";
int size = sizeof(patterns) / sizeof(patterns[0]);
printf("%d\n", countSubstrings(word, patterns, size));
return 0;
}using System;
using System.Collections.Generic;
class Program
{
static int CountSubstrings(string word, List<string> patterns)
{
int count = 0;
foreach (var pattern in patterns)
{
if (word.Contains(pattern))
{
count++;
}
}
return count;
}
static void Main()
{
var patterns = new List<string> { "a", "b", "c" };
string word = "aaaaabbbbb";
Console.WriteLine(CountSubstrings(word, patterns));
}
}Python's straightforward 'in' check determines the presence of each pattern in the word, incrementing the count for each match found.
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).
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.
import re
def count_substrings_re(word, patterns):
count = 0
for pattern in patterns:
if re.search(pattern, word):
count += 1
return count
patterns = ["a", "b", "c"]
word = "aaaaabbbbb"
print(count_substrings_re(word, patterns))function countSubstringsRe(word, patterns) {
let count = 0;
patterns.forEach(pattern => {
const regex = new RegExp(pattern);
if (regex.test(word)) {
count++;
}
});
return count;
}
const patterns = ["a", "b", "c"];
const word = "aaaaabbbbb";
console.log(countSubstringsRe(word, patterns));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.
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).
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.
function numOfStrings(patterns: string[], word: string): number {
return patterns.filter(p => word.includes(p)).length;
}func numOfStrings(patterns []string, word string) (ans int) {
for _, p := range patterns {
if strings.Contains(word, p) {
ans++
}
}
return
}impl Solution {
pub fn num_of_strings(patterns: Vec<String>, word: String) -> i32 {
patterns.iter().filter(|p| word.contains(&**p)).count() as i32
}
}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. |
| 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. |
| Simulation | – |
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. |
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.