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 <= 1051 <= a.length, b.length <= 10s, a, and b contain only lowercase English letters.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.
This approach involves directly comparing each element with every other element. This method solves the problem by exploring all possible combinations without utilizing any advanced optimization techniques.
The C code iterates over every pair of elements in the array via nested loops, and checks if their sum matches the target. Upon finding a match, it prints the pair.
Time Complexity: O(n^2)
Space Complexity: O(1)
This approach leverages a hash map to store the elements and checks for the complement required to reach the target as it iterates through the array. This significantly reduces the number of checks needed compared to the brute force method.
The C code creates a simple hash table using linked lists to store previous numbers, allowing for efficient look-up of complements during iteration, thus reducing overall complexity.
Time Complexity: O(n)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) |
| Hash Map Approach | Time Complexity: O(n) |
| Default Approach | — |
| 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 |
Find Beautiful Indices in the Given Array | Part I & II | KMP Algorithm | String Matching Algorithm • Aryan Mittal • 20,815 views views
Watch 9 more video solutions →Practice Find Beautiful Indices in the Given Array I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor