# Occurrences After Bigram
**Difficulty:** EASY
[External](https://leetcode.com/problems/occurrences-after-bigram)
Canonical: https://scaleengineer.com/dsa/problems/occurrences-after-bigram
**Data structures:** String
---
## 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 <= 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.

# Approaches
## Using String Split and a Single Loop
This approach first tokenizes the entire text into an array of words using the `split` method. Then, it iterates through this array in a single pass to find the bigram (`first`, `second`) and the subsequent third word. It's straightforward to implement and highly readable, but it uses extra space to hold the array of all words from the text.
**Time:** O(L), where L is the length of the `text` string. The `split` operation takes O(L) time. The subsequent loop runs `n` times (where `n` is the number of words), and the total work inside the loop is also proportional to L, making the overall time complexity linear. · **Space:** O(L), where L is the length of the `text` string. The `words` array created by `split` requires space proportional to the length of the text. The result list can also grow up to O(L) in the worst case.
**Pros:** Very simple and easy to understand and implement.; Code is clean and readable due to the use of high-level functions like `split`.; Efficient time complexity for the given constraints.
**Cons:** Uses extra space proportional to the length of the input text to store the array of words, which can be inefficient for very large texts.
### Explanation
The most intuitive way to solve this problem is to treat the text as a sequence of words. The `String.split(" ")` method in Java is perfect for this, as it breaks the text into an array of words based on the space delimiter. Once we have this array, the problem is reduced to finding a specific two-element sequence.

We can iterate through the array, looking at a window of three consecutive words at a time: `(words[i], words[i+1], words[i+2])`. For each window, we check if the first two words match the input `first` and `second`. If they do, we add the third word of the window, `words[i+2]`, to our list of results. The loop needs to stop before the end of the array to prevent an `IndexOutOfBoundsException`, specifically at the third-to-last element.

After checking all possible positions, the list of collected 'third' words is converted into an array and returned.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public String[] findOcurrences(String text, String first, String second) {
        String[] words = text.split(" ");
        List<String> result = new ArrayList<>();
        
        // We need at least 3 words to find a "first second third" sequence.
        if (words.length < 3) {
            return new String[0];
        }
        
        // Iterate up to the third-to-last word.
        for (int i = 0; i <= words.length - 3; i++) {
            // Check if the current bigram matches.
            if (words[i].equals(first) && words[i+1].equals(second)) {
                // If it matches, add the next word to the result.
                result.add(words[i+2]);
            }
        }
        
        // Convert the list to a String array for the final output.
        return result.toArray(new String[0]);
    }
}
```
### Algorithm
1. Split the input `text` string by spaces to get an array of words, let's call it `words`.
2. Initialize an empty list, `result`, to store the found words.
3. Check if the `words` array has fewer than three elements. If so, return an empty array as a bigram occurrence is impossible.
4. Iterate through the `words` array from index `i = 0` up to `words.length - 3`.
5. In each iteration, check if `words[i]` is equal to `first` and `words[i+1]` is equal to `second`.
6. If the condition is true, it means we've found the pattern `first second`, so we add the following word, `words[i+2]`, to our `result` list.
7. After the loop completes, convert the `result` list into a string array.
8. Return the resulting array.

## Manual Parsing with State Tracking
This approach avoids splitting the entire string into an array at once, which makes it more space-efficient. It iterates through the text character by character, manually identifying words. It maintains a state of the two previously seen words and checks for the pattern as each new word is parsed. This uses constant extra space (besides the result list), making it optimal in terms of memory.
**Time:** O(L), where L is the length of the `text` string. We iterate through the string once. Operations inside the loop like `substring` and `equals` contribute to a total time that is linear in the length of the text. · **Space:** O(W + R), where W is the maximum length of a word and R is the total length of the words in the result. The auxiliary space for storing `word1` and `word2` is O(W), which is effectively O(1) given the constraints on word length. This is more efficient than the O(L) space used by the split approach.
**Pros:** Extremely space-efficient, using O(1) auxiliary space (excluding the storage for the result).; Processes the text in a single pass without needing to store all words in memory.
**Cons:** The implementation is more complex and requires careful management of indices and state.; The code is less readable and more prone to off-by-one errors compared to the `split` approach.
### Explanation
Instead of creating an intermediate array of all words, we can process the text in a stream-like fashion. We iterate through the string, building up words as we go. The problem constraints (single spaces, no leading/trailing spaces) simplify this parsing.

We maintain two state variables, `word1` and `word2`, representing the last two words encountered. As we parse the text and identify a `currentWord`, we check if the state `(word1, word2)` matches the target `(first, second)`. If it does, we add `currentWord` to our results. After each word is processed, we update our state by shifting the words: `word1` takes the value of `word2`, and `word2` takes the value of `currentWord`. This sliding window of two words allows us to find the pattern in a single pass with minimal memory overhead.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public String[] findOcurrences(String text, String first, String second) {
        List<String> result = new ArrayList<>();
        String word1 = null;
        String word2 = null;
        
        int wordStart = 0;
        for (int i = 0; i <= text.length(); i++) {
            // A word ends at a space or at the end of the string.
            if (i == text.length() || text.charAt(i) == ' ') {
                String currentWord = text.substring(wordStart, i);
                
                // Check if the previous two words form the target bigram.
                if (word1 != null && word2 != null && word1.equals(first) && word2.equals(second)) {
                    result.add(currentWord);
                }
                
                // Slide the window of the two most recent words.
                word1 = word2;
                word2 = currentWord;
                
                // Set the start for the next word.
                wordStart = i + 1;
            }
        }
        
        return result.toArray(new String[0]);
    }
}
```
### Algorithm
1. Initialize two string variables, `word1` and `word2`, to `null` to store the two most recent words.
2. Initialize an empty list `result` to store the third words.
3. Use a pointer, `wordStart`, initialized to 0, to mark the beginning of the current word being parsed.
4. Iterate through the `text` string with an index `i` from 0 to `text.length()`.
5. If the character at `i` is a space, or if `i` has reached the end of the string, a word has been fully identified.
   a. Extract the `currentWord` using `text.substring(wordStart, i)`.
   b. Check if `word1` and `word2` are not null and if they match `first` and `second` respectively.
   c. If they match, add `currentWord` to the `result` list.
   d. Update the history by shifting the words: `word1` becomes `word2`, and `word2` becomes `currentWord`.
   e. Update `wordStart` to `i + 1` to point to the beginning of the next word.
6. After the loop, convert the `result` list to a string array and return it.

# Solutions
### Java

```java
class Solution {
public
  String[] findOcurrences(String text, String first, String second) {
    String[] words = text.split(" ");
    List<String> ans = new ArrayList<>();
    for (int i = 0; i < words.length - 2; ++i) {
      if (first.equals(words[i]) && second.equals(words[i + 1])) {
        ans.add(words[i + 2]);
      }
    }
    return ans.toArray(new String[0]);
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> findOcurrences(string text, string first, string second) {
    istringstream is(text);
    vector<string> words;
    string word;
    while (is >> word) {
      words.emplace_back(word);
    }
    vector<string> ans;
    int n = words.size();
    for (int i = 0; i < n - 2; ++i) {
      if (words[i] == first && words[i + 1] == second) {
        ans.emplace_back(words[i + 2]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findOcurrences(self, text: str, first: str, second: str) -> List[str]: words = text . split() ans = [] for i in range(len(words) - 2): a, b, c = words[i: i + 3] if a == first and b == second: ans . append(c) return ans

```