Number of Strings That Appear as Substrings in Word

Number of Strings That Appear as Substrings in Word - Problem

Array String Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: patterns = ["a","aa","aaa"], word = "aaaa"

› Output: 3

💡 Note: All patterns are substrings: "a" appears at positions 0,1,2,3; "aa" appears at positions 0,1,2; "aaa" appears at positions 0,1

Example 2 — Partial Matches

$ Input: patterns = ["a","b","c"], word = "aaaaabbbbb"

› Output: 2

💡 Note: "a" and "b" are found in word, but "c" is not present

Example 3 — No Matches

$ Input: patterns = ["a","a","a"], word = "ab"

› Output: 3

💡 Note: All three patterns "a" exist in word "ab", even though they're duplicates

Constraints

1 ≤ patterns.length ≤ 100
1 ≤ patterns[i].length ≤ 100
1 ≤ word.length ≤ 100
patterns[i] and word consist of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

Array of patterns and target word

Process

Check each pattern as substring in word

Output

Count of patterns found

Key Takeaway

🎯 Key Insight: Use built-in substring methods to efficiently count pattern occurrences

Asked in

a Amazon 15 G Google 12 M Microsoft 8

This problem asks us to count how many strings in an array appear as substrings in a target word. The key insight is to use built-in substring search methods for efficiency. Best approach is the Built-in Substring Search which gives us clean, readable code. Time: O(n×m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Built-in Substring Search	O(n × m)	O(1)	Use language built-in substring search methods for each pattern
Brute Force Character Matching	O(n × m × k)	O(1)	Manually check each pattern at every position in word using nested loops

Built-in Substring Search — Algorithm Steps

Iterate through each pattern in the array
Use built-in substring search to check if pattern exists in word
Count patterns that are found
Return the total count

Visualization

Tap to expand

Step-by-Step Walkthrough

Pattern Check

Use built-in method to check each pattern

Quick Search

Language optimized search finds matches

Count Result

Increment counter for each found pattern

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char patterns[][100], int patternCount, char* word) {
    int count = 0;
    for (int i = 0; i < patternCount; i++) {
        if (strstr(word, patterns[i]) != NULL) {
            count++;
        }
    }
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse JSON array manually
    char patterns[100][100];
    int patternCount = 0;
    char* token = strtok(line + 1, ","); // Skip opening bracket
    while (token != NULL) {
        // Remove quotes and whitespace
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"' || *end == ']')) end--;
        *(end + 1) = 0;
        strcpy(patterns[patternCount], token);
        patternCount++;
        token = strtok(NULL, ",");
    }
    
    char word[1000];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    int result = solution(patterns, patternCount, word);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n patterns × m word length, built-in substring search is optimized but still O(m) per pattern

✓ Linear Growth

Space Complexity

O(1)

Only using a counter variable, no extra data structures

✓ Linear Space

25.0K Views

Medium Frequency

~5 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Built-in Substring Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler