Occurrences After Bigram
EasyPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Split the input
textstring by spaces to get an array of words, let's call itwords. - Initialize an empty list,
result, to store the found words. - Check if the
wordsarray has fewer than three elements. If so, return an empty array as a bigram occurrence is impossible. - Iterate through the
wordsarray from indexi = 0up towords.length - 3. - In each iteration, check if
words[i]is equal tofirstandwords[i+1]is equal tosecond. - If the condition is true, it means we've found the pattern
first second, so we add the following word,words[i+2], to ourresultlist. - After the loop completes, convert the
resultlist into a string array. - Return the resulting array.
Walkthrough
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.
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]); }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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]); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.