Sliding Window Substring Count | Dataford Interview Questions

Warner Bros. Discovery may need to count occurrences of a marker in text processed for HBO Max search or content tooling. Given a text string and a pattern string, return how many times the pattern occurs in the text, including overlapping occurrences.

A match starts at every index where the complete pattern equals the corresponding text window. Return 0 when the pattern is empty or does not occur. The input is case-sensitive.

Formal Specification

Implement count_pattern_occurrences(text, pattern).

Input: text, a string of length n, and pattern, a string of length m.
Output: An integer representing the number of valid starting positions of pattern in text.
Overlapping matches must be counted separately.
Do not use Python's built-in substring-counting methods.

Constraints

0 <= len(text) <= 10^6
0 <= len(pattern) <= 10^5
Both strings contain printable ASCII characters
Overlapping occurrences must be counted
Do not use built-in substring-counting methods
Target complexity is O(n + m) time and O(m) auxiliary space

Function Signature

def count_pattern_occurrences(text, pattern):

Your question is Sliding Window Substring Count. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem