Problem Description

You are given a string text containing multiple words separated by spaces. You need to find patterns where three consecutive words appear in a specific sequence.

Given two strings first and second, you need to:

1. Look for occurrences where first appears as a word, immediately followed by second as the next word
2. When you find such a pattern, capture the third word that immediately follows second
3. Return all such third words in an array

For example, if text = "alice is a good girl she is a good student", first = "a", and second = "good":

• The pattern "a good" appears twice in the text
• After the first occurrence "a good", the next word is "girl"
• After the second occurrence "a good", the next word is "student"
• So you would return ["girl", "student"]

The solution works by:

1. Splitting the text into individual words using text.split()
2. Iterating through the words array with a sliding window of size 3
3. Checking if the first two words in the window match first and second respectively
4. If they match, adding the third word to the result array
5. The loop stops at len(words) - 2 to ensure we always have three words to examine

Intuition

The key insight is that we're looking for a pattern of three consecutive words where the first two words are fixed (given as first and second), and we need to collect all possible third words that complete this pattern.

Since we're dealing with words in a text, the natural first step is to split the text into individual words. This transforms our problem from string matching to array traversal, which is much simpler to handle.

Once we have an array of words, we can think of this as a sliding window problem. We need to examine every possible sequence of three consecutive words in the text. For each triplet of words (a, b, c), we check if a matches first and b matches second. If both conditions are met, then c is one of our answers.

Why do we iterate only until len(words) - 2? Because we need to examine groups of three words at each position. If we start at position i, we look at words at positions i, i+1, and i+2. The last valid starting position is therefore len(words) - 3, which means we iterate while i < len(words) - 2.

The beauty of this approach is its simplicity - we don't need complex string matching algorithms or regular expressions. By converting the problem to word-level matching instead of character-level, we avoid complications like partial word matches or dealing with word boundaries. Each word is treated as a distinct unit, making the comparison straightforward with the == operator.

Solution Approach

The implementation follows a straightforward linear scan approach with a sliding window pattern:

1. Text Preprocessing: First, we split the input text into an array of words using text.split(). This built-in method handles multiple spaces and gives us clean word tokens to work with.

2. Initialize Result Container: We create an empty list ans to store all the third words that match our pattern.

3. Sliding Window Traversal: We iterate through the words array with index i from 0 to len(words) - 2. At each position, we extract a window of three consecutive words:

   a, b, c = words[i : i + 3]

   This slice operation words[i : i + 3] gives us exactly three words starting from index i.

4. Pattern Matching: For each triplet (a, b, c), we check if the pattern matches:

   if a == first and b == second:
       ans.append(c)

   When both conditions are satisfied (first word equals first and second word equals second), we add the third word c to our result list.

5. Return Results: After scanning through all possible positions, we return the collected list of third words.

The time complexity is O(n) where n is the number of words in the text, as we visit each word position once. The space complexity is O(n) for storing the split words array, plus O(k) for the result where k is the number of matching patterns found.

This solution elegantly handles edge cases:

• If the text has fewer than 3 words, the loop doesn't execute and returns an empty list
• Multiple occurrences of the pattern are all captured
• The same third word can appear multiple times in the result if the pattern occurs multiple times

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input:

• text = "I love to code and love to learn"
• first = "love"
• second = "to"

Step 1: Split the text into words

words = ["I", "love", "to", "code", "and", "love", "to", "learn"]

Step 2: Initialize result container

ans = []

Step 3: Iterate with sliding window (i from 0 to len(words) - 2 = 6)

• i = 0: Extract triplet ["I", "love", "to"]

  • a = "I", b = "love", c = "to"
  • Check: a == "love"? No → skip

• i = 1: Extract triplet ["love", "to", "code"]

  • a = "love", b = "to", c = "code"
  • Check: a == "love"? Yes, b == "to"? Yes → Match found!
  • Add "code" to ans: ans = ["code"]

• i = 2: Extract triplet ["to", "code", "and"]

  • a = "to", b = "code", c = "and"
  • Check: a == "love"? No → skip

• i = 3: Extract triplet ["code", "and", "love"]

  • a = "code", b = "and", c = "love"
  • Check: a == "love"? No → skip

• i = 4: Extract triplet ["and", "love", "to"]

  • a = "and", b = "love", c = "to"
  • Check: a == "love"? No → skip

• i = 5: Extract triplet ["love", "to", "learn"]

  • a = "love", b = "to", c = "learn"
  • Check: a == "love"? Yes, b == "to"? Yes → Match found!
  • Add "learn" to ans: ans = ["code", "learn"]

Step 4: Return result

return ["code", "learn"]

The pattern "love to" appears twice in the text, followed by "code" and "learn" respectively, which are both captured in our result.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input string text.

• The text.split() operation takes O(n) time to split the string into words
• The for loop iterates through len(words) - 2 iterations, which is O(m) where m is the number of words
• Inside each iteration, slicing words[i : i + 3] takes O(1) time since it always slices exactly 3 elements
• The string comparisons a == first and b == second take O(1) time on average (assuming constant-length words)
• The append() operation takes amortized O(1) time
• Since the number of words m is proportional to the length of the text n, the overall time complexity is O(n)

Space Complexity: O(n) where n is the length of the input string text.

• The words list stores all words from the split operation, requiring O(n) space to store all characters from the input text
• The ans list stores the result, which in the worst case could contain up to O(m) words where m is the number of words in the text
• The temporary variables a, b, c use O(1) space
• Since the total space used is dominated by storing the split words, the overall space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Multiple Consecutive Spaces

One common pitfall is assuming that text.split() and text.split(' ') behave identically. When the input text contains multiple consecutive spaces or leading/trailing spaces, using text.split(' ') can create empty strings in the words array, leading to incorrect pattern matching.

Problem Example:

text = "alice  is   a good girl"  # Multiple spaces between words
first = "a"
second = "good"

# Wrong approach:
words = text.split(' ')  # Results in ['alice', '', 'is', '', '', 'a', 'good', 'girl']

# Correct approach:
words = text.split()     # Results in ['alice', 'is', 'a', 'good', 'girl']

Solution: Always use text.split() without arguments, which automatically handles multiple spaces, tabs, and newlines as delimiters and filters out empty strings.

2. Case Sensitivity Issues

Another pitfall occurs when the problem requirements are unclear about case sensitivity. The current solution is case-sensitive, meaning "Good" and "good" are treated as different words.

Problem Example:

text = "Alice is A Good girl she is a good student"
first = "a"
second = "good"
# This would only match "a good" but not "A Good"

Solution: If case-insensitive matching is required, normalize the case:

def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
    words = text.split()
    first_lower = first.lower()
    second_lower = second.lower()
    result = []
  
    for i in range(len(words) - 2):
        word_1, word_2, word_3 = words[i:i + 3]
        if word_1.lower() == first_lower and word_2.lower() == second_lower:
            result.append(word_3)  # Return original case
  
    return result

3. Not Validating Input Assumptions

A subtle pitfall is not considering edge cases in the input, such as empty strings or single-word inputs.

Problem Example:

text = ""  # Empty string
# or
text = "word"  # Single word
# or
text = "first second"  # Only two words when we need three

Solution: While the current implementation handles these gracefully (the loop simply doesn't execute), it's good practice to explicitly check:

def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
    if not text or not first or not second:
        return []
  
    words = text.split()
    if len(words) < 3:
        return []
  
    # Continue with the main logic...

4. Overlapping Pattern Consideration

A less obvious pitfall is not recognizing that patterns can overlap when the same word appears multiple times consecutively.

Problem Example:

text = "a a a a"
first = "a"
second = "a"
# The patterns "a a a" overlap at indices 0-2 and 1-3
# Should return ["a", "a"]

The current solution correctly handles this by advancing the window one position at a time, but developers might mistakenly try to skip ahead after finding a match, missing overlapping patterns.