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 <= 1000text consists of lowercase English letters and spacesall words in text are separated by a single space, with no leading or trailing spaces1 <= first.length, second.length <= 10first and second consist of lowercase English letters
Hints for Occurrences After Bigram
Hint 1
Split the sentence into words first.
Hint 2
Look at every window of three consecutive words.
Hint 3
If the window's first two words are
firstandsecond, 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
- Split
texton spaces into an arrayw. - For every
ifrom 0 whilei + 2 < w.length, ifw[i] == firstandw[i+1] == second, appendw[i+2]. - 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 == secondthe 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