Find Beautiful Indices in the Given Array II - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3008. Find Beautiful Indices in the Given Array II
Hard
50 Points
Two Pointers
String
Binary Search
Rolling Hash
String Matching
Hash Function
You are given a 0-indexed string s, a string a, a string b, and an integer k.
An index i is beautiful if:
Return the array that contains beautiful indices in sorted order from smallest to largest.
Examples
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.
Constraints
1 <= k <= s.length <= 5 * 105
1 <= a.length, b.length <= 5 * 105
s, a, and b contain only lowercase English letters.
3008. Find Beautiful Indices in the Given Array II
Hard
50 Points
Two Pointers
String
Binary Search
Rolling Hash
String Matching
Hash Function
You are given a 0-indexed string s, a string a, a string b, and an integer k.
An index i is beautiful if:
Return the array that contains beautiful indices in sorted order from smallest to largest.
Examples
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.
Constraints
1 <= k <= s.length <= 5 * 105
1 <= a.length, b.length <= 5 * 105
s, a, and b contain only lowercase English letters.