3303. 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.
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 <= 3 * 105sandpatternconsist only of lowercase English letters.
Follow-up: Could you solve the problem if at most k consecutive characters can be changed?
Solution:
class Solution {
public int minStartingIndex(String s, String pattern) {
boolean change = false;
int sIndex = 0;
int pIndex = 0;
// 1. find the substring
int diff = pattern.length();
/*
0123456 diff = 6
"abcdefg" len = 7 7 - 6 = 1
i
i+ diff 0 + 6
j
012345
"bcdffg"
*/
for (int i = 0; i < s.length() - diff + 1; i++){
boolean last = false;
pIndex = 0;
for (int j = i; j < i + diff; j++){//0<6
if (s.charAt(j) == pattern.charAt(pIndex)){
if (j == i + diff - 1){
last = true;
}
pIndex++;
continue;
}else{
if (change == true){
break;
}else{
pIndex++;
continue;
}
}
}
if (last == true){
return i;
}
}
return -1;
}
}
?????
/*
Input
s =
"ababbababa"
pattern =
"bacaba"
Output
0
Expected
*/