Find Beautiful Indices in the Given Array II
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.lengths[i..(i + a.length - 1)] == a- There exists an index
jsuch that: 0 <= j <= s.length - b.lengths[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 = 15Output
[16,33]There are 2 beautiful indices, 16 and 33, because each starts an occurrence of
a and is within distance k of an occurrence of b.Example 2
Input
s = "abcd", a = "a", b = "a", k = 4Output
[0]Index 0 is beautiful because both
a and b occur at index 0 and their distance is 0, which is at most 4.Constraints
- 1 <= k <= s.length <= 5 * 10^5
- 1 <= a.length, b.length <= 5 * 10^5
- s, a, and b contain only lowercase English letters.