Find Pattern in Infinite Stream II

Hard

Asked by:

12 views

Topics:

Strings

You are given an infinite stream of characters arriving one at a time. You are also given a string pattern. You need to find the first occurrence of the pattern in the stream.

Implement the StreamRanker class:

StreamRanker(String pattern) Initializes the StreamRanker object with the pattern string.
void add(char c) Adds a new character c to the stream.
int getRank() Return the number of characters read from the stream so far. Return -1 if pattern was not found. Return (index of the last char of pattern) + 1 if pattern was found.

Example 1:

Input
["StreamRanker", "add", "getRank", "add", "getRank", "add", "getRank", "add", "getRank", "add", "getRank", "add", "getRank", "add", "getRank"]
[["abab"], ["a"], [], ["b"], [], ["a"], [], ["b"], [], ["a"], [], ["b"], [], ["b"], []]
Output
[null, null, -1, null, -1, null, -1, null, 4, null, -1, null, 4, null, -1]

Explanation
StreamRanker streamRanker = new StreamRanker("abab");
streamRanker.add("a"); // stream = "a"
streamRanker.getRank(); // return -1
streamRanker.add("b"); // stream = "ab"
streamRanker.getRank(); // return -1
streamRanker.add("a"); // stream = "aba"
streamRanker.getRank(); // return -1
streamRanker.add("b"); // stream = "abab"
streamRanker.getRank(); // return 4, because "abab" is found at index 0
streamRanker.add("a"); // stream = "ababa"
streamRanker.getRank(); // return -1, because we want the first occurence
streamRanker.add("b"); // stream = "ababab"
streamRanker.getRank(); // return 4, because "abab" is found at index 0
streamRanker.add("b"); // stream = "abababb"
streamRanker.getRank(); // return -1

Constraints:

1 <= pattern.length <= 1000
pattern consists of only lowercase English letters.
c is a lowercase English letter.
At most 10⁵ calls will be made to add and getRank.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data type is the pattern and the elements within the infinite stream? Are we dealing with strings, integers, or something else?
If the pattern is not found within the currently processed stream, should the algorithm continue searching the stream indefinitely, or is there a defined stopping condition or maximum length of stream to process?
What should be returned if the pattern is never found within the processed portion of the infinite stream?
Can the pattern be empty, and if so, what should the algorithm return?
What constitutes a 'match'? Should the pattern be matched contiguously, or are there any allowed gaps or transformations between the elements of the pattern and the elements in the stream?

Brute Force Solution

Approach

Imagine we're searching for a secret message hidden within a long, never-ending flow of characters. The brute force method means we'll meticulously examine every possible snippet of the flow to see if it matches the secret message. We'll essentially try out all combinations, one by one, until we find it.

Here's how the algorithm would work step-by-step:

Grab the first few characters from the beginning of the flow and see if they match the secret message.
If they don't, grab a slightly longer sequence of characters from the beginning and check again.
Keep increasing the length of the sequence, checking it against the secret message each time.
Once you've checked all sequences starting from the very beginning, move one character over and repeat the process. Start checking sequences of increasing lengths from this new position.
Continue shifting the starting point and checking sequences until you reach the end of the flow (or until you are told to stop).
If, at any point, the sequence of characters exactly matches the secret message, then you've found the pattern.

Code Implementation

def find_pattern_brute_force(stream, pattern):
    stream_length = len(stream)
    pattern_length = len(pattern)

    for start_index in range(stream_length):
        # Iterate through all possible starting positions

        for end_index in range(start_index + 1, stream_length + 1):
            # Check all possible lengths of substrings starting from current position

            substring = stream[start_index:end_index]

            if len(substring) == pattern_length:
                # Only check if the substring is the same length as the pattern

                if substring == pattern:
                    # Return true if substring matches pattern
                    return True

    return False

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the length of the infinite stream we process and m be the length of the pattern we are looking for. We iterate through the stream up to n characters. For each starting position in the stream, we extract a substring of length up to m. The comparison of this substring with the pattern takes O(m) time. Since we do this for each of the n starting positions in the stream, the overall time complexity is O(n*m). Note that in an infinite stream scenario, n would be defined as the amount of processed data, making O(n*m) a reasonable representation of the cost.

Space Complexity

O(M) – The plain English explanation describes extracting sequences of increasing lengths from the infinite stream to compare against the secret message. The space complexity is dominated by the maximum length of the sequence that needs to be stored which is the length of the secret message, M. Therefore, the algorithm requires auxiliary space proportional to the length of the secret message (M) to store the currently checked sequence. Hence the space complexity can be expressed as O(M).

Optimal Solution

Approach

The key to solving this problem efficiently is to avoid storing the entire infinite stream and to use a finite state machine based on the pattern. We use the pattern to define the states and transitions, allowing us to check if the pattern exists in the stream incrementally.

Here's how the algorithm would work step-by-step:

First, think of the pattern you are searching for as a sequence of states. Each state represents a part of the pattern.
Create a starting state representing the beginning of the pattern.
As you read each element from the infinite stream, determine if it matches the expected element for transitioning from the current state to the next state in the pattern.
If the current element matches the next expected part of the pattern, move to the next state.
If the current element does not match, return to the starting state.
If you reach the end state, it means you've found the complete pattern in the stream. Report that the pattern was found and return to the beginning, in case the pattern repeats.
This process is repeated for each element in the stream without having to store any previous stream elements, making it suitable for infinite streams.

Code Implementation

def find_pattern_in_stream(stream, pattern):
    pattern_length = len(pattern)
    current_state = 0

    for element in stream:

        # Check if the current element matches the expected pattern element.
        if element == pattern[current_state]:
            current_state += 1

            # If we've reached the end of the pattern, report it.
            if current_state == pattern_length:
                print("Pattern found!")
                current_state = 0 # Reset to start, search again

        # If no match, start looking for the pattern from beginning
        else:
            current_state = 0

Big(O) Analysis

Time Complexity

O(n) – The algorithm processes each element from the infinite stream exactly once. For each element, it performs a constant amount of work: comparing the element against the expected pattern element and potentially transitioning to the next state in the pattern's finite state machine. Because each stream element is visited only once and the operations performed are constant per element, the time complexity is linearly proportional to the number of elements processed, up to a point where a pattern is declared found. Once a pattern is found, the state machine resets to the initial state and the process restarts; however, each element is still checked only once. Therefore, the time complexity is O(n) where n is the number of elements processed from the infinite stream.

Space Complexity

O(1) – The provided solution utilizes a finite state machine based on the pattern to be found. It primarily involves tracking the current state, which can be represented by a constant number of variables, specifically an index or pointer indicating the progress within the pattern. The algorithm does not store the stream itself or create any auxiliary data structures that scale with the input stream size. Therefore, the space complexity remains constant, regardless of the length of the infinite stream, leading to O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty pattern string	Return an empty list or an appropriate error code to indicate no pattern to search for.
Null or empty stream of characters	Return an empty list or an appropriate error code to indicate no input stream to search within.
Pattern longer than the available stream	Return an empty list if the stream is shorter than the pattern, as a match is impossible.
Pattern containing special characters (e.g., Unicode, control characters)	Ensure the comparison logic handles these characters correctly, especially if using language-specific string functions or regular expressions.
Extremely long pattern and stream (scalability)	Consider using an efficient string matching algorithm like Knuth-Morris-Pratt (KMP) or Boyer-Moore to avoid quadratic time complexity.
Overlapping patterns within the stream (e.g., pattern 'abab' in stream 'abababab')	Ensure the algorithm correctly identifies all occurrences of the pattern, even if they overlap.
Pattern contains repeated characters (e.g., 'aaa')	KMP algorithm needs to handle building the correct LPS array for repeated character patterns.
No match found in the stream	Return an empty list to indicate that the pattern was not found.

Null or empty pattern string

How to Handle:

Return an empty list or an appropriate error code to indicate no pattern to search for.

Null or empty stream of characters

How to Handle:

Return an empty list or an appropriate error code to indicate no input stream to search within.

Pattern longer than the available stream

How to Handle:

Return an empty list if the stream is shorter than the pattern, as a match is impossible.

Pattern containing special characters (e.g., Unicode, control characters)

How to Handle:

Ensure the comparison logic handles these characters correctly, especially if using language-specific string functions or regular expressions.

Extremely long pattern and stream (scalability)

How to Handle:

Consider using an efficient string matching algorithm like Knuth-Morris-Pratt (KMP) or Boyer-Moore to avoid quadratic time complexity.

Overlapping patterns within the stream (e.g., pattern 'abab' in stream 'abababab')

How to Handle:

Ensure the algorithm correctly identifies all occurrences of the pattern, even if they overlap.

Pattern contains repeated characters (e.g., 'aaa')

How to Handle:

KMP algorithm needs to handle building the correct LPS array for repeated character patterns.

No match found in the stream

How to Handle:

Return an empty list to indicate that the pattern was not found.