Number of Strings That Appear as Substrings in Word

Easy
1021.

Number of Strings That Appear as Substrings in Word

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.

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 <= 100
  • 1 <= patterns[i].length <= 100
  • 1 <= word.length <= 100
  • patterns[i] and word consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} patterns
 * @param {string} word
 * @return {number}
 */
var numOfStrings = function(patterns, word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • 1 <= patterns[i].length <= 100
  • 1 <= word.length <= 100
  • patterns[i] and word consist of lowercase English letters.

Hints for Number of Strings That Appear as Substrings in Word

  1. Hint 1

    Every language has a substring search — use it once per pattern.

  2. Hint 2

    A pattern longer than word can never occur.

  3. 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

  1. For each pattern, search for it inside word.
  2. 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 word counts.
  • 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings