Skip to main content
Talentd

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

HardTwo PointersStringBinary SearchRolling Hash21 min readAsked at: Palantir, Google, PhonePe
Practice this problem

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.length
  • s[i..(i + a.length - 1)] == a
  • There exists an index j such that:
    • 0 <= j <= s.length - b.length
    • s[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 <= 5 * 105
  • 1 <= a.length, b.length <= 5 * 105
  • s, a, and b contain only lowercase English letters.

Approach Overview

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.

Approach 1: Sliding Window with Hash Map

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor ā†’

Approach 2: Optimized Two-Pass Scan

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor ā†’

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
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.

Default Approachā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window with Hash MapO(n)O(n)When substring matches are tracked using hashing or rolling hash and you want simple window-based validation.
Optimized Two-Pass ScanO(n)O(n)Best general solution. Uses two pointers over sorted occurrence lists for linear verification.

Video Solution

Find Beautiful Indices in the Given Array | Part I & II | KMP Algorithm | String Matching Algorithm ā€¢ Aryan Mittal ā€¢ 21,883 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Find Beautiful Indices in the Given Array II easy or hard?
Find Beautiful Indices in the Given Array II is classified as Hard. The difficulty comes from combining efficient substring detection with a linear-time verification strategy. Recognizing that the problem reduces to scanning two sorted lists of indices is the key insight.
Find Beautiful Indices in the Given Array II Python/Java solution
Python and Java implementations typically compute all match positions of a and b, store them in lists, and then apply a two-pointer scan to check the k-distance condition. The logic is identical across languages and runs in O(n) time with O(n) space.
How to solve Find Beautiful Indices in the Given Array II in O(n)?
First detect every occurrence of a and b using rolling hash or another linear string matching technique. Store their starting indices in two arrays. Then iterate through the a indices while advancing a pointer over the b indices so that only indices within the range [iāˆ’k, i+k] are considered. Each pointer moves forward once, giving O(n) complexity.
What is the best approach for Find Beautiful Indices in the Given Array II?
The optimized two-pass scan is the most efficient approach. First collect all indices where substring a and substring b appear using linear string matching. Then use a two-pointer sweep to check whether any b index lies within k distance of each a index. This keeps the total time complexity O(n).
Is Find Beautiful Indices in the Given Array II asked at Google/Amazon/Meta?
Problems involving substring matching, rolling hash, and two-pointer scans frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine pattern matching with distance constraints are common in senior-level string processing questions.
What data structure is used in Find Beautiful Indices in the Given Array II?
The solution primarily uses arrays or lists to store occurrence indices of the substrings. Two pointers are then used to scan those sorted lists efficiently. Some implementations also use rolling hash structures to detect substring matches quickly.
What is the time complexity of Find Beautiful Indices in the Given Array II?
The optimal solution runs in O(n) time where n is the length of the string. One pass finds occurrences of substrings a and b, and another linear scan with two pointers verifies the distance condition. The space complexity is O(n) for storing occurrence indices.

Ready to solve this problem?

Practice Find Beautiful Indices in the Given Array II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Container With Most Water