Number of Strings That Appear as Substrings in Word Solution
Number of Strings That Appear as Substrings in Word solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Strings That Appear as Substrings in Word is an easy coding problem on arrays and strings, asked in Amazon, Google and Accenture interviews.
- Difficulty: Easy
- Topics: Arrays, Strings
- Asked at: Amazon, Google, Accenture
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return the number of strings in patterns that occur as a substring of word.
A substring is a contiguous run of characters.
Example 1
Input: patterns = ["code","kai","judge","ekai"], word = "codekairo"
Output: 3
Explanation: `code`, `kai` and `ekai` all occur; `judge` does not.
Example 2
Input: patterns = ["a","abc","bc","d"], word = "abc"
Output: 3
Example 3
Input: patterns = ["a","b","c"], word = "aaaaabbbbb"
Output: 2
Explanation: No `c` anywhere.
Constraints
1 <= patterns.length <= 1001 <= patterns[i].length <= 1001 <= word.length <= 100patterns[i] and word consist of lowercase English letters.
Hints for Number of Strings That Appear as Substrings in Word
Hint 1
Every language has a substring search — use it once per pattern.
Hint 2
A pattern longer than
wordcan never occur.Hint 3
Duplicated patterns each count.
How to solve Number of Strings That Appear as Substrings in Word
Test each pattern for containment in word and count the hits.
Approach
- For each pattern, search for it inside
word. - Count the patterns that are found.
Why it works
At these sizes the naïve search is fine — 100 patterns of length 100 against a word of length 100 is at most a million character comparisons. A suffix automaton of word would answer each pattern in linear time in the pattern's own length, which is the shape the problem takes at scale.
Complexity
- Time —
O(p · n · m) in the worst case - Space —
O(1)
Pitfalls
- Substring, not subsequence — the characters must be adjacent.
- A pattern equal to
wordcounts. - Repeated patterns are counted separately.
Reference solution
Python
from typing import List
def numOfStrings(patterns: List[str], word: str) -> int:
return sum(1 for p in patterns if p in word)Java
public static int numOfStrings(String[] patterns, String word) {
int count = 0;
for (String p : patterns) {
if (word.contains(p)) count++;
}
return count;
}C++
int numOfStrings(vector<string>& patterns, string word) {
int count = 0;
for (auto& p : patterns) {
if (word.find(p) != string::npos) count++;
}
return count;
}JavaScript
var numOfStrings = function(patterns, word) {
var count = 0;
for (var i = 0; i < patterns.length; i++) {
if (word.indexOf(patterns[i]) !== -1) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.