Watch 4 video solutions for Find the Occurrence of First Almost Equal Substring, a hard level problem involving String, String Matching. This walkthrough by CodeFod has 975 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two strings s and pattern.
A string x is called almost equal to y if you can change at most one character in x to make it identical to y.
Return the smallest starting index of a substring in s that is almost equal to pattern. If no such index exists, return -1.
Example 1:
Input: s = "abcdefg", pattern = "bcdffg"
Output: 1
Explanation:
The substring s[1..6] == "bcdefg" can be converted to "bcdffg" by changing s[4] to "f".
Example 2:
Input: s = "ababbababa", pattern = "bacaba"
Output: 4
Explanation:
The substring s[4..9] == "bababa" can be converted to "bacaba" by changing s[6] to "c".
Example 3:
Input: s = "abcd", pattern = "dba"
Output: -1
Example 4:
Input: s = "dde", pattern = "d"
Output: 0
Constraints:
1 <= pattern.length < s.length <= 105s and pattern consist only of lowercase English letters.Follow-up: Could you solve the problem if at most
k consecutive characters can be changed?Problem Overview: You are given a text string s and a pattern p. The task is to return the first index where a substring of s of length len(p) is almost equal to p, meaning the two strings differ in at most one character. If no such substring exists, return -1. The challenge is efficiently detecting a window where the mismatch count is ≤ 1.
Approach 1: Sliding Window Approach (O(n * m) time, O(1) space)
Scan the string using a window of length m where m = len(p). For every starting index i, compare characters in s[i ... i+m-1] with p. Count mismatches during the comparison. If the mismatch count exceeds 1, break early and move to the next window. If the count stays ≤ 1 after checking the whole pattern, return the current index. This approach uses straightforward character comparison and no extra data structures, but in the worst case each window performs m comparisons. For large strings this leads to O(n * m) time complexity.
This method relies purely on sequential scanning and is a direct application of the sliding window technique over a string. It is easy to implement and useful for understanding the baseline logic before optimizing.
Approach 2: Optimized Sliding Window with Precomputation (O(n + m) time, O(n + m) space)
The optimized solution avoids repeated comparisons by precomputing how many characters match from the left and right. First compute the longest prefix matches between p and every suffix of s. Then compute suffix matches (characters that match from the end). These arrays tell you how many characters align before and after a potential mismatch. For a window starting at i, if the prefix match length plus the suffix match length is at least m - 1, the substring differs by at most one character.
This idea is common in advanced string matching problems: instead of rechecking characters repeatedly, you precompute matching segments once and reuse them for all windows. The algorithm effectively reduces the repeated comparisons and brings the total complexity down to linear time O(n + m). The extra arrays store prefix and suffix match lengths, giving O(n + m) space usage.
Recommended for interviews: Start by explaining the brute sliding window solution since it clearly models the definition of “almost equal”. Then optimize using prefix/suffix match precomputation to reach O(n + m). Interviewers typically expect recognition that repeated substring comparisons are wasteful and can be replaced with precomputed match lengths.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Comparison | O(n * m) | O(1) | Simple baseline solution or when input sizes are small |
| Optimized Sliding Window with Precomputation | O(n + m) | O(n + m) | Large strings where repeated substring comparisons would be too slow |