Find Beautiful Indices in the Given Array II

Find Beautiful Indices in the Given Array II

What is this problem about?

The Find Beautiful Indices in the Given Array II coding problem is the optimized version of the previous challenge. The constraints are much larger, making naive string matching (indexOf) or repeated searching too slow. You still need to find indices of pattern a that are within distance k of pattern b, but the string length can be up to $5 imes 10^5$.

Why is this asked in interviews?

This "Hard" problem is used by Google and Palantir to evaluate a candidate's mastery of high-performance string algorithms. It evaluation your knowledge of the KMP (Knuth-Morris-Pratt) algorithm or Rolling Hash interview pattern. It tests whether you can implement a linear-time string matcher and then efficiently merge the resulting index lists.

Algorithmic pattern used

The solution combines KMP Algorithm and Two Pointers.

1. Linear String Matching: Use the KMP preprocessing (failure function) to find all occurrences of a and b in $O(N + M)$ time.
2. Efficient Range Search: Since both resulting index lists pos_a and pos_b are already sorted:
   • Use two pointers to iterate through pos_a and find if any j in pos_b satisfies the distance constraint.
   • For each i in pos_a, move the pos_b pointer to the first element $\ge i - k$. If that element is also $\le i + k$, then i is beautiful.

Example explanation

String: "...a...b...a...b...", $k=5$.

1. KMP finds pos_a = [10, 100, 500] and pos_b = [12, 400].
2. For $i=10$: $12$ is in $[10-5, 10+5]$. Beautiful!
3. For $i=100$: $12$ is too small, $400$ is too large. Not beautiful.
4. For $i=500$: $400$ is too small. Not beautiful. This coordination is done in one pass over the two index lists.

Common mistakes candidates make

• Slow Matching: Using string.substr() or indexOf in a loop, which is $O(N imes M)$.
• Sorting indices: Unnecessarily sorting the index lists when KMP naturally produces them in increasing order.
• Failing KMP implementation: Incorrectly building the prefix table (LPS array), which leads to incorrect matches.

Interview preparation tip

KMP is a "must-know" for Hard string problems. Practice writing the getLPS function until it becomes second nature. It's the most common way to achieve linear time in pattern matching.