Practice Find the Occurrence of First Almost Equal Substring
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Find the earliest zero-based position in s where a contiguous substring of pattern.length differs from pattern at no more than one position. An exact match qualifies too. Replacing a character is allowed; inserting or deleting characters is not. Return -1 when no qualifying substring exists. Approach: Compute, for each candidate window, its longest matching prefix with pattern and its longest matching suffix. Forward and reversed Z-function passes provide these lengths in O(s.length + pattern.length) time and space. A window qualifies when the two matching lengths sum to at least pattern.length-1. Scan starts in increasing order to return the first match, including the exact-match case. Worked example: In the first input below, the window starting at 2 is "abc". Replacing c with d matches "abd"; neither earlier window qualifies. In the second input, every window differs at two positions.
Source: Find the Occurrence of First Almost Equal Substring on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
s = "zzabcq", pattern = "abd"
2
# Example 2
s = "aaaa", pattern = "bb"
-1
Constraints
How to solve Find the Occurrence of First Almost Equal Substring
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
A window matches with at most one substitution exactly when its longest common prefix with the pattern plus its longest common suffix covers all but at most one position. Two linear Z-function passes, one forward and one on reversed strings, give both lengths for every window.
Why brute force is not enough
Comparing each of up to 10^5 windows against the pattern character by character costs window count times pattern length, nearly 10^10 operations when the pattern is almost as long as s.
Approach
- Let m be the pattern length and n the length of s. Compute the Z-function of pattern, a separator not in either string, then s. For window start i, the value at the position of s[i] is the longest common prefix of the window and the pattern.
- Reverse both strings and repeat. The value at the reversed position of the window's end gives its longest common suffix with the pattern; window i ends at i + m - 1, which maps to index n - m - i within the reversed s.
- If the prefix length p is below m, position p is a real mismatch, so the suffix match cannot cross it and p plus suffix length is at most m - 1. Equality means exactly one mismatch; p equal to m means an exact match.
- Scan window starts from 0 to n - m in increasing order and return the first i where prefix plus suffix is at least m - 1.
- Return -1 if none qualifies.
Walkthrough of Example 1
s = "zzabcq", pattern = "abd" → 2
- s is "zzabcq", pattern is "abd", so m is 3 and windows start at 0 through 3.
- Window 0 is "zza": prefix 0, suffix 0 (a versus d), total 0, below 2.
- Window 1 is "zab": prefix 0, suffix 0 (b versus d), total 0.
- Window 2 is "abc": prefix 2 (ab), suffix 0 (c versus d), total 2, which reaches m - 1 = 2.
- Return 2, the expected output; changing c to d turns the window into the pattern.
Time and space
Time O(n + m) · Space O(n + m). n is the length of s and m the pattern length; each Z-function pass is linear in the combined string and stores one array of that size.
Interview pitfalls
- Getting the reversed index mapping off by one, so the suffix length belongs to a neighboring window.
- Mishandling the exact-match case where the prefix length equals m; it must pass the test.
- Using a separator that can occur in the input, letting matches cross the boundary.
- Scanning windows past n - m, which indexes beyond s.
- Reaching for a rolling hash with binary search on the mismatch position; it works but is slower and easier to get wrong than the two Z passes.
Follow-up questions interviewers ask
- How would you generalize to at most k mismatches, and what is the complexity?
- Can the same two passes count all qualifying windows rather than only the first?
- What if one insertion or deletion were allowed as well as a substitution?
Further reading on the technique: String-searching algorithm
Related LeetCode Problems
Practice more problems similar to Find the Occurrence of First Almost Equal Substring.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.