LeetCode Solutions Blog

Find Beautiful Indices in the Given Array II

Number: 3303

Difficulty: Hard

Paid? No

Problem Description

Given a 0-indexed string s, two pattern strings a and b, and an integer k, find all indices i that are considered "beautiful". An index i is beautiful if:

i is a valid starting index for pattern a in s (i.e. 0 <= i <= s.length - a.length and s[i...i+a.length-1] equals a), and
there exists some index j such that j is a valid starting index for pattern b in s (i.e. 0 <= j <= s.length - b.length and s[j...j+b.length-1] equals b) and the absolute difference |i - j| <= k. Return the list of beautiful indices in sorted order.

Key Insights

Use an efficient string matching algorithm (like KMP or Rolling Hash) to find all occurrences of patterns a and b in s.
Store the starting indices for a and b separately.
With both lists sorted, use two pointers or binary search to quickly check for each occurrence of a whether there is a nearby occurrence of b (within distance k).
This avoids a brute force O(n*m) approach and ensures efficiency given the input constraints.

Space and Time Complexity

Time Complexity: O(n + m + Na + Nb)
• O(n + m) for pattern matching for each pattern
• O(Na + Nb) for scanning through the occurrence lists using two pointers or binary search
Space Complexity: O(Na + Nb) where Na and Nb are the number of occurrences of a and b in s, respectively.

Solution

We first find all starting indices where pattern a and b occur in s using a helper function that implements the KMP algorithm. Then, we iterate through each occurrence index of a and use a two-pointer approach (or binary search) on the sorted list of b-occurrences to check whether there is an index j such that |i - j| <= k. If such a j exists, we add i to the result list. Finally, we return the result list, sorted in ascending order.

Code Solutions

# Python solution using KMP for pattern matching and two pointers for merging occurrence lists.

def kmp_search(text, pattern):
    # Build longest prefix suffix (LPS) array for the pattern
    n, m = len(text), len(pattern)
    lps = [0] * m
    j = 0  # length of previous longest prefix suffix
    i = 1
    while i < m:
        if pattern[i] == pattern[j]:
            j += 1
            lps[i] = j
            i += 1
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                lps[i] = 0
                i += 1

    # Now, find the pattern in the text using the lps array
    occurrences = []
    i = j = 0
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                occurrences.append(i - j)
                j = lps[j - 1]
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return occurrences

def find_beautiful_indices(s, a, b, k):
    # Find all occurrence indices for a and b in s
    occurrences_a = kmp_search(s, a)
    occurrences_b = kmp_search(s, b)
    result = []
    pointer_b = 0
    len_b = len(occurrences_b)
    
    # Two pointers: for each occurrence of a, try to find a b occurrence near it.
    for idx_a in occurrences_a:
        # Move pointer_b until the occurrence is within the window or beyond
        while pointer_b < len_b and occurrences_b[pointer_b] < idx_a - k:
            pointer_b += 1
        # Check if the current pointer gives valid distance
        if pointer_b < len_b and abs(occurrences_b[pointer_b] - idx_a) <= k:
            result.append(idx_a)
        # It might be beneficial to check the previous occurrence of b (if exists) as well
        elif pointer_b - 1 >= 0 and abs(occurrences_b[pointer_b - 1] - idx_a) <= k:
            result.append(idx_a)
    return result

# Example usage:
if __name__ == "__main__":
    s = "isawsquirrelnearmysquirrelhouseohmy"
    a = "my"
    b = "squirrel"
    k = 15
    beautiful_indices = find_beautiful_indices(s, a, b, k)
    print(beautiful_indices)  # Output: [16, 33]