Find Beautiful Indices in the Given Array II - Solution & Explanation

Problem Overview: Given a string s and two patterns a and b, return all indices i where a appears in s and there exists an index j where b appears such that |i - j| ≤ k. The output must be sorted and include every valid starting index of a.

The core challenge is efficiently locating all occurrences of both substrings and quickly verifying whether any occurrence of b lies within distance k from each occurrence of a. Naively comparing every pair of indices would be too slow for large inputs, so efficient string matching and range checking are required.

Approach 1: Sliding Window with Hash Map (O(n) time, O(n) space)

First locate all occurrences of a and b in s. Efficient substring detection can be done using a rolling hash or other string matching techniques so each position is checked in constant time. Store all indices where b appears in a hash-based structure or array. Then iterate through each index where a occurs and maintain a sliding window representing the valid range [i - k, i + k]. If any stored b index falls inside that window, the index i is beautiful.

The hash-backed lookup helps quickly verify candidate positions while scanning forward. This approach works well when substring matches are already computed using a rolling hash and you want a straightforward window-based validation. Time complexity is O(n) after preprocessing and space complexity is O(n) for storing match indices.

Approach 2: Optimized Two-Pass Scan (O(n) time, O(n) space)

This approach separates the problem into two clean passes. First scan the string and record every starting index of a and b. Rolling hash or other linear-time matching ensures this step remains efficient. Once both index lists are built, process them with a two pointers technique.

Maintain a pointer on the list of b indices while iterating through each index of a. Move the pointer until the b index is within the left boundary i - k. Then check whether the current b index is ≤ i + k. Because both lists are sorted by construction, the pointer never moves backward, producing a linear pass over both lists. This eliminates repeated searches and avoids using binary search.

The two-pass strategy is typically the fastest and easiest to reason about. Each list is scanned once, so the total complexity stays O(n) with O(n) extra space for storing indices.

Recommended for interviews: The optimized two-pass scan is what interviewers usually expect. It shows that you first reduce the problem to two lists of substring matches and then apply a linear two-pointer sweep to check distance constraints efficiently. Mentioning a brute-force pair comparison demonstrates baseline understanding, but implementing the linear scan highlights algorithmic maturity and awareness of scalable string-processing techniques.