Occurrences After Bigram

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.

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public String[] findOcurrences(String text, String first, String second) {6        String[] words = text.split(" ");7        List<String> result = new ArrayList<>();8        9        // We need at least 3 words to find a "first second third" sequence.10        if (words.length < 3) {11            return new String[0];12        }13        14        // Iterate up to the third-to-last word.15        for (int i = 0; i <= words.length - 3; i++) {16            // Check if the current bigram matches.17            if (words[i].equals(first) && words[i+1].equals(second)) {18                // If it matches, add the next word to the result.19                result.add(words[i+2]);20            }21        }22        23        // Convert the list to a String array for the final output.24        return result.toArray(new String[0]);25    }26}

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.

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public String[] findOcurrences(String text, String first, String second) {6        List<String> result = new ArrayList<>();7        String word1 = null;8        String word2 = null;9        10        int wordStart = 0;11        for (int i = 0; i <= text.length(); i++) {12            // A word ends at a space or at the end of the string.13            if (i == text.length() || text.charAt(i) == ' ') {14                String currentWord = text.substring(wordStart, i);15                16                // Check if the previous two words form the target bigram.17                if (word1 != null && word2 != null && word1.equals(first) && word2.equals(second)) {18                    result.add(currentWord);19                }20                21                // Slide the window of the two most recent words.22                word1 = word2;23                word2 = currentWord;24                25                // Set the start for the next word.26                wordStart = i + 1;27            }28        }29        30        return result.toArray(new String[0]);31    }32}