Occurrences After Bigram

Occurrences After Bigram - Problem

String Easy

Given two strings first and second, consider occurrences in some text of the form "first second third", where second comes immediately after first, and third comes immediately after second.

Return an array of all the words third for each occurrence of "first second third".

Input & Output

Example 1 — Basic Pattern Matching

$ Input: text = "alice is a girl she is a student", first = "a", second = "girl"

› Output: ["she"]

💡 Note: The pattern "a girl" appears once in the text, followed by "she", so we return ["she"]

Example 2 — Multiple Occurrences

$ Input: text = "we will we will rock you", first = "we", second = "will"

› Output: ["we","rock"]

💡 Note: Pattern "we will" appears twice: first followed by "we", second followed by "rock"

Example 3 — No Matches

$ Input: text = "alice is a girl", first = "bob", second = "is"

› Output: []

💡 Note: The pattern "bob is" never appears in the text, so return empty array

Constraints

1 ≤ text.length ≤ 1000
text consists of lowercase English letters and spaces
All words in text are separated by a single space
1 ≤ first.length, second.length ≤ 10
first and second consist of lowercase English letters

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to scan through the text looking for consecutive word patterns. Split the text into words, then check each position for the bigram pattern and collect the following words. Best approach is single-pass scanning with boundary checks. Time: O(n), Space: O(m) where m is number of matches.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n)	O(m)	Check every possible starting position for the bigram pattern
Single Pass Scan	O(n)	O(m)	Optimized single-pass solution with early termination checks

Brute Force — Algorithm Steps

Step 1: Split text into words array
Step 2: For each word position i, check if words[i] == first and words[i+1] == second
Step 3: If pattern found, add words[i+2] to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Split Text

Convert text into array of words

Check Pattern

At each position, check if next two words match pattern

Collect Results

When pattern found, collect the third word

Code -

solution.c — C

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

char** solution(char* text, char* first, char* second, int* returnSize) {
    char* textCopy = strdup(text);
    char** words = malloc(1000 * sizeof(char*));
    int wordCount = 0;
    
    char* token = strtok(textCopy, " ");
    while (token != NULL) {
        words[wordCount] = strdup(token);
        wordCount++;
        token = strtok(NULL, " ");
    }
    
    char** result = malloc(1000 * sizeof(char*));
    *returnSize = 0;
    
    for (int i = 0; i <= wordCount - 3; i++) {
        if (strcmp(words[i], first) == 0 && strcmp(words[i + 1], second) == 0) {
            result[*returnSize] = strdup(words[i + 2]);
            (*returnSize)++;
        }
    }
    
    free(textCopy);
    for (int i = 0; i < wordCount; i++) {
        free(words[i]);
    }
    free(words);
    
    return result;
}

int main() {
    char text[10000], first[100], second[100];
    fgets(text, sizeof(text), stdin);
    fgets(first, sizeof(first), stdin);
    fgets(second, sizeof(second), stdin);
    
    text[strcspn(text, "\n")] = 0;
    first[strcspn(first, "\n")] = 0;
    second[strcspn(second, "\n")] = 0;
    
    int returnSize;
    char** result = solution(text, first, second, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
        free(result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the text array checking each position

✓ Linear Growth

Space Complexity

O(m)

Result array stores m matching third words

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

285 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

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler