Find Beautiful Indices in the Given Array I - Video Solutions
Find Beautiful Indices in the Given Array | Part I & II | KMP Algorithm | String Matching Algorithm
Find Beautiful Indices in the Given Array I - Video Solution
Watch 10 video solutions for Find Beautiful Indices in the Given Array I, a medium level problem involving Two Pointers, String, Binary Search. This walkthrough by Aryan Mittal has 21,883 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 = 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 <= 1051 <= a.length, b.length <= 10s,a, andbcontain only lowercase English letters.
Approach Overview
Problem Overview: You are given a string s and two substrings a and b. An index i is considered beautiful if substring a starts at i and there exists another index j where substring b starts such that |i - j| ≤ k. The task is to return all beautiful indices in sorted order.
Approach 1: Brute Force String Matching (O(n * m + p * q), Space O(n))
Scan the string and record every index where substring a appears and every index where substring b appears. This uses direct substring comparison while iterating through s. After collecting both index lists, check every a index against every b index and verify whether |i - j| ≤ k. If the condition holds for any j, mark i as beautiful. The method is simple and demonstrates understanding of string matching, but the nested comparison becomes expensive when both lists are large.
Approach 2: Hash Map + Binary Search on Indices (O(n log n), Space O(n))
First iterate through the string once and store all starting indices of substring a and b. The indices where b occurs are kept in a sorted list. For each index i where a appears, perform a binary search on the b index list to locate the closest position to i. Then check whether the nearest index satisfies |i - j| ≤ k. Binary search reduces the comparison from scanning the entire list to O(log n) per check. This pattern is common in problems combining binary search with preprocessed index lists.
The key idea is separating discovery and validation. First find all pattern occurrences using straightforward substring checks (or faster techniques like rolling hash if needed). Then efficiently verify distance constraints using sorted indices. This reduces redundant comparisons and keeps the algorithm scalable even when the string length grows.
Recommended for interviews: The binary search approach is the expected solution. Interviewers want to see that you preprocess substring occurrences and avoid quadratic comparisons. Starting with the brute force method shows understanding of the problem, but transitioning to the optimized method demonstrates stronger algorithmic thinking and familiarity with two pointer or search-based optimizations.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force String Matching | O(n * m + p * q) | O(n) | Good for understanding the problem or when input size is small |
| Hash Map + Binary Search | O(n log n) | O(n) | Best general solution when substring occurrences must be checked within a distance constraint |