Occurrences After Bigram

Difficulty: Easy | Acceptance: 63.90% | Paid: No Topics: String

Given two strings first and second, consider occurrences in some text of values “first second third”, where second comes immediately after first, and third comes immediately after second.

For each such occurrence, add “third” to the answer, and return the answer.

• Examples
• Constraints
• Split and Iterate
• String Search
• Regular Expression

Examples

Input: text = "alice is a good girl she is a good student", first = "a", second = "good"
Output: ["girl","student"]
Explanation: "a" comes before "good" and "girl" is the word after "good". Also "a" comes before "good" and "student" is the word after "good".

Input: text = "we will we will rock you", first = "we", second = "will"
Output: ["we","rock"]

Constraints

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

Split and Iterate

Intuition Split the text into words and iterate through them, checking if each consecutive pair matches the bigram.

Steps

• Split the text into an array of words
• Iterate through words from index 0 to length-3
• If current word equals first and next word equals second, add the word after to result
• Return the result array

class Solution:
    def findOcurrences(self, text: str, first: str, second: str) -> list[str]:
        words = text.split()
        result = []
        for i in range(len(words) - 2):
            if words[i] == first and words[i + 1] == second:
                result.append(words[i + 2])
        return result

Complexity

• Time: O(n) where n is the number of words
• Space: O(n) for storing the split words
• Notes: Simple and readable, most commonly used approach

String Search

Intuition Search for the pattern “first second ” in the text and extract the word immediately following each match.

Steps

• Build the search pattern by concatenating first, space, second, and space
• Use string find/indexOf to locate all occurrences of the pattern
• For each match, extract the word starting right after the pattern
• Continue searching from the next position

class Solution:
    def findOcurrences(self, text: str, first: str, second: str) -> list[str]:
        result = []
        pattern = first + " " + second + " "
        start = 0
        while True:
            idx = text.find(pattern, start)
            if idx == -1:
                break
            word_start = idx + len(pattern)
            word_end = word_start
            while word_end < len(text) and text[word_end] != ' ':
                word_end += 1
            result.append(text[word_start:word_end])
            start = idx + 1
        return result

Complexity

• Time: O(n × m) where n is text length and m is pattern length
• Space: O(k) where k is the number of matches
• Notes: Avoids splitting entire string, useful for very large texts

Regular Expression

Intuition Use regex pattern matching to find all occurrences of “first second word” and capture the third word.

Steps

• Build a regex pattern that matches first, whitespace, second, whitespace, and captures the next word
• Use regex findall/exec to get all matches
• Extract the captured group from each match
• Return the array of captured words

import re

class Solution:
    def findOcurrences(self, text: str, first: str, second: str) -> list[str]:
        pattern = re.escape(first) + r'\s+' + re.escape(second) + r'\s+(\w+)'
        matches = re.findall(pattern, text)
        return matches

Complexity

• Time: O(n) where n is the text length
• Space: O(k) where k is the number of matches
• Notes: Most concise solution, handles special characters in search terms