Find the Occurrence of First Almost Equal Substring - Solution & Explanation
Problem Statement
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 <= 105sandpatternconsist only of lowercase English letters.
Follow-up: Could you solve the problem if at most
k consecutive characters can be changed?Approach Overview
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 1: Sliding Window Approach
This approach uses a sliding window technique to evaluate every possible substring of 's' that matches the length of 'pattern'. For each substring, we compare it to 'pattern' and count how many characters are different. If the difference in characters is 1 or less, we've found our answer. This method is efficient because it only requires a single pass through 's'.
The function find_almost_equal_substring receives two strings, s and pattern. It iterates through all possible starting indices of s (that can form valid substrings of length equal to pattern). For each such starting index, it counts the number of differing characters between the substring and pattern. If this count is less than or equal to 1, it returns the starting index; otherwise, it continues until the end. If no valid index is found, it returns -1.
Complexity
Time Complexity: O(M*N) - where M is the length of 's' and N is the length of 'pattern'.
Space Complexity: O(1) - only a fixed number of additional variables are used.
Approach 2: Optimized Sliding Window with Precomputation
This approach improves the efficiency by maintaining a count of differences between the current window and the pattern and updates it as the window slides. We precompute the initial differences and then use those to adjust efficiently as the window moves, decreasing unnecessary recalculations.
In the find_almost_equal_substring_optimized function, we first calculate the number of differing characters between the initial substring and the pattern. As we slide the window over the string, we adjust the number of differing characters by adding one for a difference at the new character introduced and subtracting one for the character removed.
Complexity
Time Complexity: O(M)
Space Complexity: O(1)
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(M*N) - where M is the length of 's' and N is the length of 'pattern'. Space Complexity: O(1) - only a fixed number of additional variables are used. |
| Optimized Sliding Window with Precomputation | Time Complexity: O(M) Space Complexity: O(1) |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode Biweekly Contest 140 | 3303. Find the Occurrence of First Almost Equal Substring | Easiest • CodeFod • 994 views views
Watch 3 more video solutions →Frequently Asked Questions
Is Find the Occurrence of First Almost Equal Substring easy or hard?
Find the Occurrence of First Almost Equal Substring Python/Java solution
How to solve Find the Occurrence of First Almost Equal Substring in O(n)?
What is the best approach for Find the Occurrence of First Almost Equal Substring?
Is Find the Occurrence of First Almost Equal Substring asked at Google/Amazon/Meta?
What data structure is used in Find the Occurrence of First Almost Equal Substring?
What is the time complexity of Find the Occurrence of First Almost Equal Substring?
Ready to solve this problem?
Practice Find the Occurrence of First Almost Equal Substring with our built-in code editor and test cases.
Practice on FleetCode