Find the Occurrence of First Almost Equal Substring
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.
A substring is a contiguous non-empty sequence of characters within a string.
Follow-up: Could you solve the problem if at most k consecutive characters can be changed?
Example 1
Input
s = "abcdefg", pattern = "bcdffg"Output
1The substring
s[1..6] == "bcdefg" can be converted to "bcdffg" by changing s[4] to "f".Example 2
Input
s = "ababbababa", pattern = "bacaba"Output
4The substring
s[4..9] == "bababa" can be converted to "bacaba" by changing s[6] to "c".Constraints
- 1 <= pattern.length < s.length <= 10^5
- s and pattern consist only of lowercase English letters.