3303. Find the Occurrence of First Almost Equal Substring Hard

1/**
2 * [3303] Find the Occurrence of First Almost Equal Substring
3 *
4 * You are given two strings s and pattern.
5 * 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.
6 * Return the smallest starting index of a <span data-keyword="substring-nonempty">substring</span> in s that is almost equal to pattern. If no such index exists, return -1.
7 * A substring is a contiguous non-empty sequence of characters within a string.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">s = "abcdefg", pattern = "bcdffg"</span>
12 * Output: <span class="example-io">1</span>
13 * Explanation:
14 * The substring s[1..6] == "bcdefg" can be converted to "bcdffg" by changing s[4] to "f".
15 * </div>
16 * <strong class="example">Example 2:
17 * <div class="example-block">
18 * Input: <span class="example-io">s = "ababbababa", pattern = "bacaba"</span>
19 * Output: <span class="example-io">4</span>
20 * Explanation:
21 * The substring s[4..9] == "bababa" can be converted to "bacaba" by changing s[6] to "c".
22 * </div>
23 * <strong class="example">Example 3:
24 * <div class="example-block">
25 * Input: <span class="example-io">s = "abcd", pattern = "dba"</span>
26 * Output: <span class="example-io">-1</span>
27 * </div>
28 * <strong class="example">Example 4:
29 * <div class="example-block">
30 * Input: <span class="example-io">s = "dde", pattern = "d"</span>
31 * Output: <span class="example-io">0</span>
32 * </div>
33 *  
34 * Constraints:
35 * 
36 * 	1 <= pattern.length < s.length <= 10^5
37 * 	s and pattern consist only of lowercase English letters.
38 * 
39 *  
40 * Follow-up: Could you solve the problem if at most k consecutive characters can be changed?
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/find-the-occurrence-of-first-almost-equal-substring/
45// discuss: https://leetcode.com/problems/find-the-occurrence-of-first-almost-equal-substring/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn min_starting_index(s: String, pattern: String) -> i32 {
51        0
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_3303() {
63    }
64}
65