Skip to main content
Talentd

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

MediumTwo PointersStringBinary SearchRolling Hash14 min readAsked at: Microsoft, Palantir, Samsara +2
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 <= 105
  • 1 <= a.length, b.length <= 10
  • s, a, and b contain 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.

Approach 1: Brute Force Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Hash Map Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

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
Brute Force Approach

Time Complexity: O(n^2)
Space Complexity: O(1)

Hash Map Approach

Time Complexity: O(n)
Space Complexity: O(n)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force String MatchingO(n * m + p * q)O(n)Good for understanding the problem or when input size is small
Hash Map + Binary SearchO(n log n)O(n)Best general solution when substring occurrences must be checked within a distance constraint

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 I easy or hard?
The problem is typically rated Medium because it combines substring matching with an efficient search constraint. The logic is straightforward once you realize that preprocessing the indices and using binary search avoids quadratic comparisons.
How to solve Find Beautiful Indices in the Given Array I in O(n)?
An O(n) style solution can be approximated by scanning the string once to record occurrences of substrings a and b, then using two pointers over the sorted index lists to maintain the distance constraint. This avoids repeated binary searches and keeps checks linear after preprocessing.
Find Beautiful Indices in the Given Array I Python or Java solution
In Python or Java, iterate through the string and collect indices of substring a and b using substring comparison. Store b indices in a list, then use binary search (bisect in Python or Collections.binarySearch in Java) to locate the nearest index within distance k.
What is the best approach for Find Beautiful Indices in the Given Array I?
The most efficient approach stores all indices where substring b appears and then checks each occurrence of substring a using binary search. This allows you to quickly find the closest b index and verify whether the distance is within k. The overall complexity becomes O(n log n) with O(n) extra space.
What data structure is used in Find Beautiful Indices in the Given Array I?
The main structure is a list or array storing all indices where substring b appears. Because the indices are naturally sorted during traversal, binary search can be applied efficiently to find the closest match for each a occurrence.
What is the time complexity of Find Beautiful Indices in the Given Array I?
The brute force method can reach O(n^2) behavior when every occurrence of substring a is compared with every occurrence of substring b. The optimized approach uses binary search on sorted indices of b and runs in O(n log n) time with O(n) space.
Is Find Beautiful Indices in the Given Array I asked at Google, Amazon, or Meta?
Problems involving substring matching with distance constraints are common in interviews at companies like Amazon, Google, and Meta. They test knowledge of string processing, index preprocessing, and efficient searching techniques such as binary search or two pointers.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Container With Most Water