Find Beautiful Indices in the Given Array I

Find Beautiful Indices in the Given Array I

What is this problem about?

The Find Beautiful Indices in the Given Array I interview question asks you to find all "beautiful" indices i in a string s. An index i is beautiful if:

1. s[i...i+a.length()-1] == a
2. There exists an index j such that s[j...j+b.length()-1] == b and $|i - j| \le k$. Basically, you need to find all occurrences of pattern a that have at least one occurrence of pattern b within distance k.

Why is this asked in interviews?

Companies like Palantir and Samsara use this problem to test your string matching and search optimization skills. It evaluation whether you can efficiently find patterns and then coordinate the results of two different searches. While the "I" version allows for less optimal solutions, the String Matching interview pattern is a core part of many data analysis and log processing tasks.

Algorithmic pattern used

This problem is solved using String Matching and Binary Search (or Two Pointers).

1. Find all starting indices where pattern a appears in s. Store them in a sorted list pos_a.
2. Find all starting indices where pattern b appears in s. Store them in a sorted list pos_b.
3. For each index i in pos_a:
   • Check if there is any j in pos_b such that i - k <= j <= i + k.
   • This check can be done efficiently using Binary Search (lower_bound or bisect_left) on the sorted list pos_b.

Example explanation

s = "isabcdeisabf", a = "ab", b = "is", k = 4

1. pos_a: [2, 9] (occurrences of "ab").
2. pos_b: [0, 7] (occurrences of "is").
3. Check index 2 from pos_a:
   • Is there a j in pos_b s.t. $|2-j| \le 4$? Yes, $j=0$ works. 2 is beautiful.
4. Check index 9 from pos_a:
   • Is there a j in pos_b s.t. $|9-j| \le 4$? Yes, $j=7$ works. 9 is beautiful. Result: [2, 9].

Common mistakes candidates make

• $O(N^2)$ search: Comparing every occurrence of a with every occurrence of b without using binary search or two pointers.
• Incorrect string matching: Using inefficient methods to find patterns in very large strings.
• Off-by-one errors: Getting the window $[i-k, i+k]$ boundaries wrong.

Interview preparation tip

When coordinating two sets of indices, always sort them first. Once sorted, you can use binary search to check for existence in logarithmic time, which is a standard way to optimize nested loops.