3303. Find the Occurrence of First Almost Equal Substring LeetCode Solution
In this guide, you will get 3303. Find the Occurrence of First Almost Equal Substring LeetCode Solution with the best time and space complexity. The solution to Find the Occurrence of First Almost Equal Substring problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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”.
1 <= pattern.length < s.length <= 105
s and pattern consist only of lowercase English letters.
Follow-up: Could you solve the problem if at most k consecutive characters can be changed?
Complexity Analysis
Time Complexity: O(|\texttt{s}| + |\texttt{pattern}|)
Space Complexity: O(|\texttt{s}| + |\texttt{pattern}|)
3303. Find the Occurrence of First Almost Equal Substring LeetCode Solution in C++
class Solution {
public:
int minStartingIndex(string s, string pattern) {
const vector<int> z1 = zFunction(pattern + s);
const vector<int> z2 = zFunction(reversed(pattern) + reversed(s));
// Match s[i..i + len(pattern) - 1] with `pattern` from both the prefix and
// the suffix.
for (int i = 0; i <= s.length() - pattern.length(); ++i)
if (z1[pattern.length() + i] + z2[s.length() - i] >= pattern.length() - 1)
return i;
return -1;
}
private:
// Returns the z array, where z[i] is the length of the longest prefix of
// s[i..n) which is also a prefix of s.
//
// https://cp-algorithms.com/string/z-function.html#implementation
vector<int> zFunction(const string& s) {
const int n = s.length();
vector<int> z(n);
int l = 0;
int r = 0;
for (int i = 1; i < n; ++i) {
if (i < r)
z[i] = min(r - i, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return z;
}
string reversed(const string& s) {
return {s.rbegin(), s.rend()};
}
}; /* code provided by PROGIEZ */
3303. Find the Occurrence of First Almost Equal Substring LeetCode Solution in Java
class Solution {
public int minStartingIndex(String s, String pattern) {
int[] z1 = zFunction(new StringBuilder(pattern).append(s).toString());
int[] z2 = zFunction(new StringBuilder(pattern)
.reverse() //
.append(new StringBuilder(s).reverse())
.toString());
// Match s[i..i + len(pattern) - 1] with `pattern` from both the prefix and
// the suffix.
for (int i = 0; i <= s.length() - pattern.length(); ++i)
if (z1[pattern.length() + i] + z2[s.length() - i] >= pattern.length() - 1)
return i;
return -1;
}
// Returns the z array, where z[i] is the length of the longest prefix of
// s[i..n) which is also a prefix of s.
//
// https://cp-algorithms.com/string/z-function.html#implementation
private int[] zFunction(final String s) {
final int n = s.length();
int[] z = new int[n];
int l = 0;
int r = 0;
for (int i = 1; i < n; ++i) {
if (i < r)
z[i] = Math.min(r - i, z[i - l]);
while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i]))
++z[i];
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return z;
}
private String reversed(String s) {
return new StringBuilder(s).reverse().toString();
}
} // code provided by PROGIEZ
3303. Find the Occurrence of First Almost Equal Substring LeetCode Solution in Python
class Solution:
def minStartingIndex(self, s: str, pattern: str) -> int:
z1 = self._zFunction(pattern + s)
z2 = self._zFunction(pattern[::-1] + s[::-1])
# Match s[i..i + len(pattern) - 1] with `pattern` from both the prefix and
# the suffix.
for i in range(len(s) - len(pattern) + 1):
if z1[len(pattern) + i] + z2[len(s) - i] >= len(pattern) - 1:
return i
return -1
def _zFunction(self, s: str) -> list[int]:
"""
Returns the z array, where z[i] is the length of the longest prefix of
s[i..n) which is also a prefix of s.
https://cp-algorithms.com/string/z-function.html#implementation
"""
n = len(s)
z = [0] * n
l = 0
r = 0
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > r:
l = i
r = i + z[i]
return z # code by PROGIEZ
