Occurrences After Bigram solution and explanation
Google
9 more videos on this problem
LeetCode 140 Problem 1 - Occurrences After Bigramcode_report · 11:11 · 4K views
1078. Occurrences After Bigram (Leetcode Easy)Programming Live with Larry · 12:17 · 252 views
1078. Occurrences After Bigram || In JAVA || Leetcode Problem || Easy Way #leetcodeQuick Learning With Sree · 7:33 · 229 views
LeetCode Algorithms Easy: Occurrences After BigramMike the Coder · 4:19 · 159 views
1078. Occurrences After Bigram | Leetcode | In TamilUI Gems (React.js, Angular, Front end interview) · 4:34 · 158 views
Occurrences After Bigram - LeetCode 1078 - Java Solutionalgobest - Computer Science · 1:35 · 115 views
Occurrences After Bigram using Sliding WindowKnowledge Amplifier · 7:58 · 112 views
1078. Occurrences After Bigram | Python + Leetcode Technical Interview PracticeDC / AC · 13:35 · 99 views
1078. Occurrences After Bigram with Python | Leetcode with Python #youtube #leetcode #pythonArsalan Ahmed · 7:00 · 46 views
1078. Occurrences After Bigram with JavaScript | Leetcode With Javascript #leetcode #youtubeArsalan Ahmed · 7:06 · 42 views
The problem
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".
Example 1:
Input: text = "alice is a good girl she is a good student", first = "a", second = "good" Output: ["girl","student"]
Example 2:
Input: text = "we will we will rock you", first = "we", second = "will" Output: ["we","rock"]
Constraints:
1 <= text.length <= 1000textconsists of lowercase English letters and spaces.- All the words in
textare separated by a single space. 1 <= first.length, second.length <= 10firstandsecondconsist of lowercase English letters.textwill not have any leading or trailing spaces.
Approach overview
Problem Overview: You receive a string text and two words first and second. The goal is to return every word that appears immediately after the sequence first second in the text. In other words, whenever the text contains the bigram first second, capture the next word.
Approach 1: Sliding Window Approach (Time: O(n), Space: O(1) excluding output)
Split the sentence into an array of words, then scan it using a window of size three. At each index i, check whether words[i] == first and words[i+1] == second. If the condition holds, append words[i+2] to the result list. This works because every valid answer must appear exactly two positions after the start of the bigram. The algorithm performs a single pass over the words array, making it an efficient linear-time solution using simple iteration.
This technique is a classic pattern from string processing problems where you scan contiguous tokens with a fixed-size window. Since the algorithm only tracks a few variables while iterating, the auxiliary space remains constant.
Approach 2: Index Mapping with HashMap (Time: O(n), Space: O(n))
Another approach builds an index structure that maps each word pair to the list of words that follow it. Iterate through the words array and construct a key such as (words[i], words[i+1]). Store words[i+2] in a map entry for that pair. After preprocessing, retrieving the answer becomes a single hash lookup for the pair (first, second).
This approach uses a hash map to precompute relationships between adjacent words. It becomes useful if the same text is queried multiple times with different bigrams because the preprocessing step allows constant-time lookups afterward. The tradeoff is higher memory usage since all bigram relationships are stored.
Conceptually, this technique resembles building adjacency relationships in string or token streams. Each pair of words acts as a key that points to possible next tokens.
Recommended for interviews: The sliding window solution is the expected answer. It is simple, readable, and runs in O(n) time with minimal space. Interviewers want to see that you recognize the pattern of scanning adjacent words and checking a fixed window. Mentioning the hash map indexing idea demonstrates deeper thinking about preprocessing and repeated queries, but the sliding window implementation is the most practical for a single query.
Approach 1: Sliding Window Approach
This approach involves scanning through the list of words using a simple loop and checking each consecutive triplet of words. If a triplet matches the pattern 'first second third', the third word is added to the result list. This method directly inspects each triplet consecutively and checks for the match with 'first' and 'second'.
def find_ocurrences(text, first, second):
words = text.split()
res = []
for i in range(len(words) - 2):
if words[i] == first and words[i + 1] == second:
res.append(words[i + 2])
return resimport java.util.*;
public class Solution {
public List<String> findOcurrences(String text, String first, String second) {
String[] words = text.split(" ");
List<String> result = new ArrayList<>();
for (int i = 0; i < words.length - 2; i++) {
if (words[i].equals(first) && words[i+1].equals(second)) {
result.add(words[i+2]);
}
}
return result;
}
}#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
vector<string> findOcurrences(string text, string first, string second) {
vector<string> words;
stringstream ss(text);
string word;
while (ss >> word) {
words.push_back(word);
}
vector<string> result;
for (size_t i = 0; i < words.size() - 2; i++) {
if (words[i] == first && words[i+1] == second) {
result.push_back(words[i+2]);
}
}
return result;
}function findOccurrences(text, first, second) {
const words = text.split(' ');
const result = [];
for (let i = 0; i < words.length - 2; i++) {
if (words[i] === first && words[i + 1] === second) {
result.push(words[i + 2]);
}
}
return result;
}#include <stdio.h>
#include <string.h>
void findOccurrences(char* text, char* first, char* second) {
char* word = strtok(text, " ");
char* prev = NULL;
char* preprev = NULL;
while (word) {
if (preprev && strcmp(preprev, first) == 0 && strcmp(prev, second) == 0) {
printf("%s\n", word);
}
preprev = prev;
prev = word;
word = strtok(NULL, " ");
}
}using System;
using System.Collections.Generic;
public class Solution {
public IList<string> FindOcurrences(string text, string first, string second) {
string[] words = text.Split(' ');
List<string> result = new List<string>();
for (int i = 0; i < words.Length - 2; i++) {
if (words[i] == first && words[i + 1] == second) {
result.Add(words[i + 2]);
}
}
return result;
}
}We first split the text into words. Then, iterate over the list of words, checking each group of three consecutive words. If the first two words match the given 'first' and 'second', we add the third word to the result list.
Time Complexity: O(n), where n is the number of words in the text.
Space Complexity: O(n) for storing the words list.
Approach 2: Index Mapping with HashMap
This method involves creating a mapping of all occurrences of each word in the text, storing their indices in a hashmap. This way, comparisons can be done only when needed, reducing unnecessary checks.
from collections import defaultdict
def find_ocurrences(text, first, second):
words = text.split()
indices = defaultdict(list)
for i, word in enumerate(words):
indices[word].append(i)
res = []
if first in indices and second in indices:
for i in indices[first]:
if i + 1 < len(words) and words[i + 1] == second:
if i + 2 < len(words):
res.append(words[i + 2])
return resimport java.util.*;
public class Solution {
public List<String> findOcurrences(String text, String first, String second) {
String[] words = text.split(" ");
Map<String, List<Integer>> indices = new HashMap<>();
for (int i = 0; i < words.length; i++) {
indices.computeIfAbsent(words[i], k -> new ArrayList<>()).add(i);
}
List<String> result = new ArrayList<>();
if (indices.containsKey(first) && indices.containsKey(second)) {
for (int i : indices.get(first)) {
if (i + 1 < words.length && words[i + 1].equals(second)) {
if (i + 2 < words.length) {
result.add(words[i + 2]);
}
}
}
}
return result;
}
}#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
vector<string> findOcurrences(string text, string first, string second) {
vector<string> words;
string word;
for (char &ch : text) {
if (ch == ' ') {
words.push_back(word);
word.clear();
} else {
word += ch;
}
}
if (!word.empty()) words.push_back(word);
unordered_map<string, vector<int>> indices;
for (int i = 0; i < words.size(); ++i) {
indices[words[i]].push_back(i);
}
vector<string> result;
for (const int &i : indices[first]) {
if (i + 1 < words.size() && words[i + 1] == second && i + 2 < words.size()) {
result.push_back(words[i + 2]);
}
}
return result;
}function findOccurrences(text, first, second) {
const words = text.split(' ');
const map = new Map();
for (let i = 0; i < words.length; i++) {
if (!map.has(words[i])) {
map.set(words[i], []);
}
map.get(words[i]).push(i);
}
const result = [];
if (map.has(first) && map.has(second)) {
for (const i of map.get(first)) {
if (i + 1 < words.length && words[i + 1] === second) {
if (i + 2 < words.length) {
result.push(words[i + 2]);
}
}
}
}
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<string> FindOcurrences(string text, string first, string second) {
string[] words = text.Split(' ');
Dictionary<string, List<int>> indices = new Dictionary<string, List<int>>();
for (int i = 0; i < words.Length; i++) {
if (!indices.ContainsKey(words[i])) {
indices[words[i]] = new List<int>();
}
indices[words[i]].Add(i);
}
List<string> result = new List<string>();
if (indices.ContainsKey(first) && indices.ContainsKey(second)) {
foreach (int i in indices[first]) {
if (i + 1 < words.Length && words[i + 1] == second) {
if (i + 2 < words.Length) {
result.Add(words[i + 2]);
}
}
}
}
return result;
}
}First, we split the text and map each word to its indices in the text. By iterating over the indices of 'first', we can look ahead to find 'second' and 'third'. This reduces the total number of comparisons to only when both words appear consecutively.
Time Complexity: O(n), where n is the number of words.
Space Complexity: O(n), due to the hashmap storing word indices.
Approach 3: Default Approach
function findOcurrences(text: string, first: string, second: string): string[] {
const words = text.split(' ');
const n = words.length;
const ans: string[] = [];
for (let i = 0; i < n - 2; i++) {
if (words[i] === first && words[i + 1] === second) {
ans.push(words[i + 2]);
}
}
return ans;
}func findOcurrences(text string, first string, second string) (ans []string) {
words := strings.Split(text, " ")
n := len(words)
for i := 0; i < n-2; i++ {
if words[i] == first && words[i+1] == second {
ans = append(ans, words[i+2])
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), where n is the number of words in the text. |
| Index Mapping with HashMap | Time Complexity: O(n), where n is the number of words. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Best for a single query on the text. Simple scan with minimal memory. |
| Index Mapping with HashMap | O(n) | O(n) | Useful when the same text is queried many times with different bigrams. |
Frequently asked questions
Is Occurrences After Bigram easy or hard?
Occurrences After Bigram is rated Easy on LeetCode with an acceptance rate above 60%. The challenge mainly tests basic string splitting, iteration, and recognizing patterns in consecutive words.
Occurrences After Bigram Python/Java solution
In Python or Java, the common approach is to split the text into words and iterate with an index. When words[i] equals first and words[i+1] equals second, add words[i+2] to the result list. The logic remains identical across Python, Java, C++, C#, and JavaScript.
How to solve Occurrences After Bigram in O(n)?
Split the input text into a list of words and iterate from index 0 to n-3. At each step, check whether words[i] equals first and words[i+1] equals second. If both match, append words[i+2] to the result. This single linear scan guarantees O(n) time complexity.
What is the best approach for Occurrences After Bigram?
The sliding window approach is the most efficient and straightforward solution. Split the text into words and scan with a window of three consecutive words. Whenever the first two match the given bigram, add the third word to the result. This runs in O(n) time and uses O(1) extra space.
Is Occurrences After Bigram asked at Google/Amazon/Meta?
Occurrences After Bigram is categorized as an easy string processing problem on LeetCode. Variations of token scanning and pattern detection appear in interviews at companies like Amazon and Google, especially when testing basic string manipulation and iteration skills.
What data structure is used in Occurrences After Bigram?
The primary data structure is an array or list of words obtained by splitting the input string. The alternative solution also uses a hash map that maps a pair of words (a bigram) to the list of words that follow it.
What is the time complexity of Occurrences After Bigram?
The optimal solution runs in O(n) time, where n is the number of words in the text. The algorithm performs a single pass through the array of words and checks adjacent elements. Space complexity is O(1) excluding the output list.