algoadvance

Leetcode 1078. Occurrences After Bigram

Problem Statement

Given words “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.

For each such occurrence, add “third” to the answer, and return the answer.

Example:

Input: text = "alice is a good girl she is a good student", first = "a", second = "good"
Output: ["girl", "student"]

Clarifying Questions

  1. Q: Can the input text contain punctuation marks? A: The problem statement implies it’s a simplified case with only words separated by spaces.

  2. Q: Is the text case-sensitive? A: The problem statement does not specify otherwise. Let’s assume it is case-sensitive.

  3. Q: Can the occurrences of “first”, “second” and “third” overlap? A: No, based on the problem description, “third” must come immediately after “second”, which comes immediately after “first”.

  4. Q: How long can the input text be? A: Typical constraints for similar problems suggest that it can go up to 10^4 characters, but for practical purposes, we assume a reasonable length within typical input limits.

Strategy

  1. Split the input text into an array of words using spaces as the delimiter.
  2. Traverse the array while checking for sequences where a word matches first, followed by a word matching second. If such a sequence is found, the subsequent word is considered third and added to the result list.
  3. Return the list of “third” words.

Code

Here is the Java code to solve the problem:

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

public class Solution {
    public String[] findOcurrences(String text, String first, String second) {
        List<String> result = new ArrayList<>();
        String[] words = text.split(" ");
        
        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.toArray(new String[result.size()]);
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] result = sol.findOcurrences("alice is a good girl she is a good student", "a", "good");
        for(String str : result) {
            System.out.println(str);
        }
    }
}

Time Complexity

The time complexity of this approach is O(n), where n is the number of words in the input text. This is because we are processing each word exactly once in a single pass of the array.

Explanation

  1. Splitting Text: text.split(" ") will create an array of words.
  2. Iteration: We iterate over the array from the start to length - 2 to ensure there are at least three words available for comparison.
  3. Comparison: For each valid triplet sequence, we check if the first and second words match the given first and second. If they do, the third word in the sequence is added to the result list.
  4. Conversion: Finally, we convert the list to an array and return it.

This solution guarantees efficient handling with minimal overhead and a clear linear scan of the input data.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI