Identifying Pattern Substrings — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the Identifying Pattern Substrings problem optimally.
O(n log n)O(n)Problem Description
You are provided with a text string s and a specific pattern string p. Your task is to determine the length of the longest contiguous substring of s that satisfies two conditions: first, the substring must appear at least twice in s (overlapping occurrences are permitted); second, the substring must contain p as a contiguous subsequence.
If no such substring exists, return 0. The solution must efficiently handle large input sizes, implying that a brute-force approach checking all possible substrings is infeasible. You must identify the maximum length L such that there exists a substring of length L in s that contains p and has at least two distinct starting indices where it occurs.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Identifying Pattern Substrings"
WHY DOES IT MATTER?
Detecting repeated substrings that embed a given pattern is a core sub‑problem in plagiarism detection, DNA motif search, and log‑analysis where you need a frequent context containing a critical token.
OPTIMIZATION CHALLENGE
The breakthrough is to decouple the two constraints: use a suffix structure to enumerate all repeated substrings in O(n) and a separate pre‑processed next‑p array to answer “does this substring contain p?” in O(1). Binary searching the length or scanning states in descending order then yields the maximal feasible length without enumerating every candidate.
REAL-WORLD CONNECTION
Imagine a distributed cache that stores query results. You want the largest cache key (substring) that is requested at least twice and always includes a mandatory security token (p). Efficiently finding that key reduces cache miss rates while guaranteeing compliance.
When coding, first build the suffix array (or automaton) and the LCP array, then compute nextP[i] = smallest j ≥ i where s[j…j+|p|‑1]==p (or INF). During the feasibility check, slide a window of size L over the LCP groups and verify nextP within the window – this keeps the inner loop linear.
COMPLEXITY AT A GLANCE
O(n log n)O(n)Core Theory — Why This Approach?
The problem asks for the longest substring of s that (1) occurs at least twice (overlap allowed) and (2) contains p as a contiguous block. A naïve solution enumerates every possible substring, checks its frequency with a hash map, and scans for p – O(n³) time – which explodes for |s| up to 10⁵. The optimal paradigm combines two classic string‑processing tools: a suffix data structure (suffix automaton or suffix array) to enumerate all repeated substrings in linear or near‑linear time, and a pre‑computed occurrence array for p to verify the containment constraint in O(1). By binary‑searching the answer length L and testing feasibility in O(n) using the suffix array’s LCP array together with the “next‑p‑position” array, we achieve O(n log n) overall, which is optimal for the given constraints. The suffix automaton offers an O(n) alternative: each state stores the maximal length of substrings it represents and the number of end‑positions (occurrence count). Propagating the earliest and latest end‑positions lets us test whether any substring of that state spans a p‑occurrence, yielding a linear‑time solution.
Interview Questions on This Problem
Q1How would you modify the solution if the substring must appear at least K times instead of twice?
In a suffix automaton, each state already stores the number of end‑positions (occurrence count). After building the automaton, propagate counts from longer to shorter states. Then during the final scan, consider only states with count ≥ K and that also cover a p‑occurrence. The answer is the maximum length among those states. The overall complexity stays O(n).
Q2Can the problem be solved in O(n) time without binary search? If so, outline the approach.
Yes. Build a suffix automaton for s. For each state, keep the minimum and maximum end‑position of substrings it represents. A substring of length ℓ in that state spans positions [min‑ℓ+1, max]. Using the pre‑computed array nextP[i] (the nearest start of p at or after i), we can check if there exists i such that i ≤ max‑ℓ+1 and nextP[i] ≤ i+ℓ‑|p|. If true, ℓ is feasible. Iterate states in decreasing order of length and keep the largest ℓ that satisfies both the count≥2 and the p‑containment test. This yields O(n) time and O(n) space.
Q3Why does allowing overlapping occurrences simplify the counting of repeated substrings?
When overlaps are permitted, any two suffixes that share a common prefix of length L automatically imply the existence of a substring of length L occurring at least twice, regardless of their start indices. Thus we only need to examine LCP values between adjacent suffixes in the sorted suffix array (or states in the automaton) without extra bookkeeping for non‑overlapping constraints.
Examples
Input
s = "ababab", p = "ab"
Output
4
Explanation: The substring "abab" appears at index 0 and index 2. It contains "ab". Length is 4. "ababa" appears only once. "babab" appears only once. Thus, 4 is the maximum.
Input
s = "abcabcabc", p = "bc"
Output
6
Explanation: The substring "abcabc" appears at index 0 and index 3. It contains "bc". Length is 6. "bcabc" appears at index 1 and 4, length 5. "abcabca" appears only once. Thus, 6 is the maximum.
Input
s = "aaaaa", p = "aa"
Output
4
Explanation: The substring "aaaa" appears at index 0 and index 1. It contains "aa". Length is 4. "aaaaa" appears only once. Thus, 4 is the maximum.
Input
s = "xyzxyz", p = "z"
Output
6
Explanation: The substring "xyzxyz" appears only once. The substring "xyz" appears at index 0 and 3. It contains "z". Length is 3. "yzxy" appears only once. "xyzx" appears only once. Wait, let's re-evaluate. "xyz" occurs at 0 and 3. Length 3. Is there a longer one? "yzxyz" occurs only once. "xyzxy" occurs only once. So the answer is 3.
Constraints
- 1 <= s.length <= 10^5
- 1 <= p.length <= s.length
- s and p consist of lowercase English letters only
- p is guaranteed to be a substring of s
Optimal Approach & Strategy
Build a suffix array (or automaton) to get all repeated substrings in O(n log n) (or O(n)), pre‑compute next‑p positions, then binary‑search the length and verify feasibility in linear time per check.
Brute Force Approach
Enumerate every possible substring, count its occurrences with a hash map, and test if it contains p – O(n³) time.
Code Solutions
/**
* @param {string} s
* @param {string} p
* @return {number}
*/
var longestPatternSubstring = function(s, p) {
const n = s.length;
const m = p.length;
if (n === 0 || m === 0) return 0;
let low = 0, high = n, ans = 0;
const check = (len) => {
if (len === 0) return true;
const seen = new Set();
for (let i = 0; i <= n - len; i++) {
const sub = s.substring(i, i + len);
if (sub.includes(p)) {
if (seen.has(sub)) {
return true;
}
seen.add(sub);
}
}
return false;
};
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (check(mid)) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
};class Solution {
public:
int longestPatternSubstring(string s, string p) {
int n = s.size();
int m = p.size();
if (n == 0 || m == 0) return 0;
// Binary search on the length of the substring
int low = 0, high = n, ans = 0;
auto check = [&](int len) -> bool {
if (len == 0) return true;
unordered_set<string> seen;
for (int i = 0; i <= n - len; ++i) {
string sub = s.substr(i, len);
// Check if the substring contains the pattern p
if (sub.find(p) != string::npos) {
if (seen.count(sub)) {
return true;
}
seen.insert(sub);
}
}
return false;
};
while (low <= high) {
int mid = low + (high - low) / 2;
if (check(mid)) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
};class Solution {
public int longestPatternSubstring(String s, String p) {
int n = s.length();
int m = p.length();
if (n == 0 || m == 0) return 0;
int low = 0, high = n, ans = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (check(s, p, mid)) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
private boolean check(String s, String p, int len) {
if (len == 0) return true;
int n = s.length();
Set<String> seen = new HashSet<>();
for (int i = 0; i <= n - len; i++) {
String sub = s.substring(i, i + len);
if (sub.contains(p)) {
if (seen.contains(sub)) {
return true;
}
seen.add(sub);
}
}
return false;
}
}class Solution:
def longestPatternSubstring(self, s: str, p: str) -> int:
n = len(s)
m = len(p)
if n == 0 or m == 0:
return 0
low, high, ans = 0, n, 0
def check(length):
if length == 0:
return True
seen = set()
for i in range(n - length + 1):
sub = s[i:i+length]
if p in sub:
if sub in seen:
return True
seen.add(sub)
return False
while low <= high:
mid = (low + high) // 2
if check(mid):
ans = mid
low = mid + 1
else:
high = mid - 1
return ans/**
* @param {string} s
* @param {string} p
* @return {number}
*/
var longestPatternSubstring = function(s, p) {
const n = s.length;
const m = p.length;
if (n === 0 || m === 0) return 0;
let low = 0, high = n, ans = 0;
const check = (len) => {
if (len === 0) return true;
const seen = new Set();
for (let i = 0; i <= n - len; i++) {
const sub = s.substring(i, i + len);
if (sub.includes(p)) {
if (seen.has(sub)) {
return true;
}
seen.add(sub);
}
}
return false;
};
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (check(mid)) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
};Asked 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.