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

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

✓ Brute Force Character Matching

⏱️ Time: O(n × m × k) Space: O(1)

For each pattern, check at every position in word if the pattern matches by comparing characters one by one. This approach implements substring matching from scratch without using built-in methods.

Built-in Substring Search

⏱️ Time: O(n × m) Space: O(1)

Iterate through each pattern and use the language's built-in substring search method (like Python's 'in' operator or JavaScript's includes()) to check if the pattern exists in the word. This is the most practical approach.

Brute Force Character Matching — Algorithm Steps

Iterate through each pattern
For each pattern, check at every position in word
Compare characters manually to find matches
Count successful matches

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Pattern

Take first pattern and check at each position

Character Match

Compare characters one by one

Count Matches

Increment count when pattern found

Code -

solution.c — C

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

int solution(char patterns[][1000], int patternCount, char* word) {
    int count = 0;
    int wordLen = strlen(word);
    
    for (int p = 0; p < patternCount; p++) {
        int patternLen = strlen(patterns[p]);
        int found = 0;
        
        // Check at every position in word
        for (int i = 0; i <= wordLen - patternLen; i++) {
            int match = 1;
            // Compare characters manually
            for (int j = 0; j < patternLen; j++) {
                if (word[i + j] != patterns[p][j]) {
                    match = 0;
                    break;
                }
            }
            if (match) {
                found = 1;
                break;
            }
        }
        if (found) {
            count++;
        }
    }
    return count;
}

void parseJsonArray(const char* line, char patterns[][1000], int* patternCount) {
    *patternCount = 0;
    if (strlen(line) < 2) return;
    
    const char* p = line + 1; // Skip opening bracket
    char current[1000];
    int pos = 0;
    int inQuotes = 0;
    
    while (*p && *p != ']') {
        if (*p == '"') {
            if (inQuotes) {
                // End of string
                current[pos] = '\0';
                strcpy(patterns[*patternCount], current);
                (*patternCount)++;
                pos = 0;
                inQuotes = 0;
            } else {
                // Start of string
                inQuotes = 1;
            }
        } else if (inQuotes) {
            current[pos++] = *p;
        }
        p++;
    }
}

void parseJsonString(const char* line, char* result) {
    if (line[0] == '"' && line[strlen(line)-1] == '"') {
        strncpy(result, line + 1, strlen(line) - 2);
        result[strlen(line) - 2] = '\0';
    } else {
        strcpy(result, line);
    }
}

int main() {
    char patternsLine[10000];
    char wordLine[10000];
    
    fgets(patternsLine, sizeof(patternsLine), stdin);
    patternsLine[strcspn(patternsLine, "\n")] = 0;
    
    fgets(wordLine, sizeof(wordLine), stdin);
    wordLine[strcspn(wordLine, "\n")] = 0;
    
    char patterns[1000][1000];
    int patternCount;
    parseJsonArray(patternsLine, patterns, &patternCount);
    
    char word[10000];
    parseJsonString(wordLine, word);
    
    int result = solution(patterns, patternCount, word);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × k)

n patterns × m word length × k average pattern length for character comparisons

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, 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

Number of Strings That Appear as Substrings in Word - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Character Matching — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler