Find Beautiful Indices in the Given Array I - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3006. Find Beautiful Indices in the Given Array I
Medium
30 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 <= 105
1 <= a.length, b.length <= 10
s, a, and b contain only lowercase English letters.
3006. Find Beautiful Indices in the Given Array I
Medium
30 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 <= 105
1 <= a.length, b.length <= 10
s, a, and b contain only lowercase English letters.