Occurrences After Bigram

Easy
1178.

Occurrences After Bigram

Occurrences After Bigram is an easy coding problem on strings and sliding window, asked in Amazon and Google interviews.

You are given a sentence text (lowercase words separated by single spaces) and two words first and second.

Whenever three consecutive words of text read first second third — first immediately followed by second, immediately followed by some word third — that third word is an occurrence.

Return every such third word, in the order they appear in text. Occurrences may overlap, and the same word may be returned more than once.

Example 1

Input
text = "kairo solves bugs kairo solves duels", first = "kairo", second = "solves"
Output
["bugs","duels"]

Example 2

Input
text = "we we we we", first = "we", second = "we"
Output
["we","we"]
Explanation
The windows starting at the first and second words both match.

Example 3

Input
text = "code fast", first = "code", second = "fast"
Output
[]
Explanation
Nothing follows the bigram.

Constraints

  • 1 <= text.length <= 1000
  • text consists of lowercase English letters and spaces
  • all words in text are separated by a single space, with no leading or trailing spaces
  • 1 <= first.length, second.length <= 10
  • first and second consist of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} text
 * @param {string} first
 * @param {string} second
 * @return {string[]}
 */
var findOcurrences = function(text, first, second) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Occurrences After Bigram — Solution in Python, Java & C++

Occurrences After Bigram solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Occurrences After Bigram is an easy coding problem on strings and sliding window, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Strings, Sliding Window
  • Asked at: Amazon, Google
  • 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

You are given a sentence text (lowercase words separated by single spaces) and two words first and second.

Whenever three consecutive words of text read first second third — first immediately followed by second, immediately followed by some word third — that third word is an occurrence.

Return every such third word, in the order they appear in text. Occurrences may overlap, and the same word may be returned more than once.

Example 1

Input: text = "kairo solves bugs kairo solves duels", first = "kairo", second = "solves"
Output: ["bugs","duels"]

Example 2

Input: text = "we we we we", first = "we", second = "we"
Output: ["we","we"]
Explanation: The windows starting at the first and second words both match.

Example 3

Input: text = "code fast", first = "code", second = "fast"
Output: []
Explanation: Nothing follows the bigram.

Constraints

  • 1 <= text.length <= 1000
  • text consists of lowercase English letters and spaces
  • all words in text are separated by a single space, with no leading or trailing spaces
  • 1 <= first.length, second.length <= 10
  • first and second consist of lowercase English letters

Hints for Occurrences After Bigram

  1. Hint 1

    Split the sentence into words first.

  2. Hint 2

    Look at every window of three consecutive words.

  3. Hint 3

    If the window's first two words are first and second, record the third — keep going even after a match, since windows overlap.

How to solve Occurrences After Bigram

After splitting into words the task is a fixed-width window: slide over every triple of consecutive words and test its first two.

Approach

  1. Split text on spaces into an array w.
  2. For every i from 0 while i + 2 < w.length, if w[i] == first and w[i+1] == second, append w[i+2].
  3. Return the collected words.

Why it works

Every occurrence is identified by the index of its first word, and the loop tries every index that has two words after it, in increasing order — so each occurrence is reported once and in text order, overlapping ones included.

Complexity

  • Time — O(|text|)
  • Space — O(|text|)

Pitfalls

  • Compare whole words, not substrings — "we" must not match inside "web".
  • Do not skip ahead after a match: with first == second the windows overlap.
  • Stop two words before the end so the third word exists.

Reference solution

Python

from typing import List

def findOcurrences(text: str, first: str, second: str) -> List[str]:
    w = text.split()
    return [w[i + 2] for i in range(len(w) - 2) if w[i] == first and w[i + 1] == second]

Java

public static String[] findOcurrences(String text, String first, String second) {
    String[] w = text.split(" ");
    List<String> res = new ArrayList<>();
    for (int i = 0; i + 2 < w.length; i++) {
        if (w[i].equals(first) && w[i + 1].equals(second)) res.add(w[i + 2]);
    }
    return res.toArray(new String[0]);
}

C++

vector<string> findOcurrences(string text, string first, string second) {
    vector<string> w;
    istringstream in1(text);
    string t;
    while (in1 >> t) w.push_back(t);
    vector<string> res;
    for (int i = 0; i + 2 < (int)w.size(); i++) {
        if (w[i] == first && w[i + 1] == second) res.push_back(w[i + 2]);
    }
    return res;
}

JavaScript

var findOcurrences = function(text, first, second) {
    var w = text.split(" ");
    var res = [];
    for (var i = 0; i + 2 < w.length; i++) {
        if (w[i] === first && w[i + 1] === second) res.push(w[i + 2]);
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Sliding Window Technique