Get started

Number of Strings That Appear as Substrings in Word — Easy Problem & Solution

Return the number of strings in patterns that occur as a substring of word. A substring is a contiguous run of characters.

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

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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue