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)] == aj such that:
0 <= j <= s.length - b.lengths[j..(j + b.length - 1)] == b|j - i| <= kReturn 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.
Constraints:
1 <= k <= s.length <= 5 * 1051 <= a.length, b.length <= 5 * 105s, a, and b contain only lowercase English letters.This approach leverages a sliding window technique along with a hash map to efficiently solve the problem. First, we iterate through the string 's' and look for occurrences of string 'b' and store their indices in a hash map. We then perform a second pass to identify all starting positions of string 'a'. For each such position, we check within the range defined by 'k' in the hash map if there's an occurrence of 'b' that satisfies all conditions for that specific position to be considered beautiful.
In this C solution, we first store all indices where 'b' starts in the string 's'. Then, we loop through 's' to find occurrences of 'a'. For each occurrence of 'a', we check if there is any stored index from 'b' that is within the distance 'k', allowing us to efficiently determine if the current index is beautiful.
C++
Java
Python
C#
JavaScript
The time complexity of this approach is O(n), where n is the length of the string 's', as we iterate over 's' twice. The space complexity is O(m), where m is the number of occurrences of 'b' stored in the array.
In this approach, we perform a two-pass scan over the string 's'. During the first pass, we identify all starting positions of the string 'a'. Simultaneously, we maintain the closest positions of string 'b' in a separate array so that for each position of 'a', we can check efficiently in constant time if there exists a position of 'b' that satisfies the distance condition. This method ensures each index checks only once, optimizing both speed and additional storage.
This C solution maintains a precomputed table where each entry remembers the most recent instance of 'b' up to that index. During the iteration of potential 'a' starting points, the precomputed table allows direct access to possible 'b' occurrences facilitating quick checks for the beautiful condition.
C++
Java
Python
C#
JavaScript
Time complexity is O(n), where n is the length of 's', as each pass over 's' is linear. Space complexity is O(n) due to the storage of closest 'b' indices.
| Approach | Complexity |
|---|---|
| Sliding Window with Hash Map | The time complexity of this approach is O(n), where n is the length of the string 's', as we iterate over 's' twice. The space complexity is O(m), where m is the number of occurrences of 'b' stored in the array. |
| Optimized Two-Pass Scan | Time complexity is O(n), where n is the length of 's', as each pass over 's' is linear. Space complexity is O(n) due to the storage of closest 'b' indices. |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,686 views views
Watch 9 more video solutions →Practice Find Beautiful Indices in the Given Array II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor