Substring Pattern Frequency ā Problem Statement & Solution Guide
Problem Description
Given a string sequence and a substring pattern, determine the total count of occurrences of pattern within sequence, where overlapping occurrences are considered valid.
Examples
Input
abcabcabc
Output
12
Explanation: Step-by-step: with input 'abcabcabc', we first find the pattern 'abc' at position 0, then at position 3, and so on, giving output 12.
Input
xyxyxy
Output
4
Explanation: Step-by-step: with input 'xyxyxy', we first find the pattern 'xy' at position 0, then at position 2, and so on, giving output 4.
Constraints
- 1 <= length of signal string <= 10^5
- 1 <= length of pattern <= 100
Optimal Approach & Strategy
The optimized approach involves using the Knuth-Morris-Pratt (KMP) algorithm or the Rabin-Karp algorithm, which are designed for string pattern matching and can handle overlaps efficiently. These algorithms preprocess the pattern to create a lookup table that allows for efficient matching, resulting in a time complexity of O(n + m).
Brute Force Approach
The brute-force approach involves using two nested loops to check every possible substring of the signal string against the pattern, resulting in a time complexity of O(nĀ²). This approach is simple but inefficient for large inputs. It can be implemented using a simple loop to iterate over the signal string and another loop to check if the pattern matches at each position.
Verified Code Solutions
public int substringPatternFrequency(String sequence, String pattern) {
int count = 0;
for (int i = 0; i <= sequence.length() - pattern.length(); i++) {
if (sequence.substring(i, i + pattern.length()).equals(pattern)) {
count++;
}
}
return count;
}def substring_pattern_frequency(sequence, pattern):
count = 0
for i in range(len(sequence)):
if sequence[i:i+len(pattern)] == pattern:
count += 1
return countAsked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.