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.

Description Hints 1 Solution Video 11:11

1078. Occurrences After Bigram

Easy64.1% acceptance1 company

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 <= 1000
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.
text will not have any leading or trailing spaces.

Asked at 1 company

Google

Topics

String

Hints open one at a time

Hint 1

Split the string into words, then look at adjacent triples of words.

11:11

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"alice is a good girl she is a good student"
"a"
"good"

Input

"we will we will rock you"
"we"
"will"

Your code is saved on this device.Solution