3006. Find Beautiful Indices in the Given Array I LeetCode Solution
In this guide, you will get 3006. Find Beautiful Indices in the Given Array I LeetCode Solution with the best time and space complexity. The solution to Find Beautiful Indices in the Given Array I 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 Beautiful Indices in the Given Array I
You are given a 0-indexed string s, a string a, a string b, and an integer k.
An index i is beautiful if:
0 <= i <= s.length – a.length
s[i..(i + a.length – 1)] == a
There exists an index j such that:
0 <= j <= s.length – b.length
s[j..(j + b.length – 1)] == b
|j – i| <= k
Return the array that contains beautiful indices in sorted order from smallest to largest.
Example 1:
Input: s = “isawsquirrelnearmysquirrelhouseohmy”, a = “my”, b = “squirrel”, k = 15
Output: [16,33]
Explanation: There are 2 beautiful indices: [16,33].
– The index 16 is beautiful as s[16..17] == “my” and there exists an index 4 with s[4..11] == “squirrel” and |16 – 4| <= 15.
– The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 – 18| <= 15.
Thus we return [16,33] as the result.
Example 2:
Input: s = "abcd", a = "a", b = "a", k = 4
Output: [0]
Explanation: There is 1 beautiful index: [0].
– The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 – 0| <= 4.
Thus we return [0] as the result.
1 <= k <= s.length <= 105
1 <= a.length, b.length <= 10
s, a, and b contain only lowercase English letters.
Complexity Analysis
Time Complexity: O(|\texttt{s}| + |\texttt{a}| + |\texttt{b}|)
Space Complexity: O(|\texttt{s}| + |\texttt{a}| + |\texttt{b}|)
3006. Find Beautiful Indices in the Given Array I LeetCode Solution in C++
class Solution {
public:
vector<int> beautifulIndices(string s, string a, string b, int k) {
vector<int> ans;
const vector<int> indicesA = kmp(s, a);
const vector<int> indicesB = kmp(s, b);
int indicesBIndex = 0; // indicesB's index
for (const int i : indicesA) {
// The constraint is: |j - i| <= k. So, -k <= j - i <= k. So, move
// `indicesBIndex` s.t. j - i >= -k, where j := indicesB[indicesBIndex].
while (indicesBIndex < indicesB.size() &&
indicesB[indicesBIndex] - i < -k)
++indicesBIndex;
if (indicesBIndex < indicesB.size() && indicesB[indicesBIndex] - i <= k)
ans.push_back(i);
}
return ans;
}
private:
// Returns the starting indices of all occurrences of the pattern in `s`.
vector<int> kmp(const string& s, const string& pattern) {
vector<int> res;
const vector<int> lps = getLPS(pattern);
int i = 0; // s' index
int j = 0; // pattern's index
while (i < s.length()) {
if (s[i] == pattern[j]) {
++i;
++j;
if (j == pattern.length()) {
res.push_back(i - j);
j = lps[j - 1];
}
} else if (j > 0) { // Mismatch after j matches.
// Don't match lps[0..lps[j - 1]] since they will match anyway.
j = lps[j - 1];
} else {
++i;
}
}
return res;
}
// Returns the lps array, where lps[i] is the length of the longest prefix of
// pattern[0..i] which is also a suffix of this substring.
vector<int> getLPS(const string& pattern) {
vector<int> lps(pattern.length());
for (int i = 1, j = 0; i < pattern.length(); ++i) {
while (j > 0 && pattern[j] != pattern[i])
j = lps[j - 1];
if (pattern[i] == pattern[j])
lps[i] = ++j;
}
return lps;
}
}; /* code provided by PROGIEZ */
3006. Find Beautiful Indices in the Given Array I LeetCode Solution in Java
class Solution {
public List<Integer> beautifulIndices(String s, String a, String b, int k) {
List<Integer> ans = new ArrayList<>();
List<Integer> indicesA = kmp(s, a);
List<Integer> indicesB = kmp(s, b);
int indicesBIndex = 0; // indicesB' index
for (final int i : indicesA) {
// The constraint is: |j - i| <= k. So, -k <= j - i <= k. So, move
// `indicesBIndex` s.t. j - i >= -k, where j := indicesB[indicesBIndex].
while (indicesBIndex < indicesB.size() && indicesB.get(indicesBIndex) - i < -k)
++indicesBIndex;
if (indicesBIndex < indicesB.size() && indicesB.get(indicesBIndex) - i <= k)
ans.add(i);
}
return ans;
}
// Returns the starting indices of all occurrences of the pattern in `s`.
private List<Integer> kmp(final String s, final String pattern) {
List<Integer> res = new ArrayList<>();
int[] lps = getLPS(pattern);
int i = 0; // s' index
int j = 0; // pattern's index
while (i < s.length()) {
if (s.charAt(i) == pattern.charAt(j)) {
++i;
++j;
if (j == pattern.length()) {
res.add(i - j);
j = lps[j - 1];
}
} else if (j != 0) { // Mismatch after j matches.
// Don't match lps[0..lps[j - 1]] since they will match anyway.
j = lps[j - 1];
} else {
++i;
}
}
return res;
}
// Returns the lps array, where lps[i] is the length of the longest prefix of
// pattern[0..i] which is also a suffix of this substring.
private int[] getLPS(final String pattern) {
int[] lps = new int[pattern.length()];
for (int i = 1, j = 0; i < pattern.length(); ++i) {
while (j > 0 && pattern.charAt(j) != pattern.charAt(i))
j = lps[j - 1];
if (pattern.charAt(i) == pattern.charAt(j))
lps[i] = ++j;
}
return lps;
}
} // code provided by PROGIEZ
3006. Find Beautiful Indices in the Given Array I LeetCode Solution in Python
class Solution:
def beautifulIndices(self, s: str, a: str, b: str, k: int) -> list[int]:
ans = []
indicesA = self._kmp(s, a)
indicesB = self._kmp(s, b)
indicesBIndex = 0 # indicesB' index
for i in indicesA:
# The constraint is: |j - i| <= k. So, -k <= j - i <= k. So, move
# `indicesBIndex` s.t. j - i >= -k, where j := indicesB[indicesBIndex].
while indicesBIndex < len(indicesB) and indicesB[indicesBIndex] - i < -k:
indicesBIndex += 1
if indicesBIndex < len(indicesB) and indicesB[indicesBIndex] - i <= k:
ans.append(i)
return ans
def _kmp(self, s: str, pattern: str) -> list[int]:
"""Returns the starting indices of all occurrences of the pattern in `s`."""
def getLPS(pattern: str) -> list[int]:
"""
Returns the lps array, where lps[i] is the length of the longest prefix of
pattern[0..i] which is also a suffix of this substring.
"""
lps = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j > 0 and pattern[j] != pattern[i]:
j = lps[j - 1]
if pattern[i] == pattern[j]:
lps[i] = j + 1
j += 1
return lps
res = []
lps = getLPS(pattern)
i = 0 # s' index
j = 0 # pattern's index
while i < len(s):
if s[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
res.append(i - j)
j = lps[j - 1]
elif j != 0: # Mismatch after j matches.
# Don't match lps[0..lps[j - 1]] since they will match anyway.
j = lps[j - 1]
else:
i += 1
return res # code by PROGIEZ
