We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Beautiful Indices in the Given Array I

Number: 3245

Difficulty: Medium

Paid? No

Companies: Palantir Technologies

Problem Description

Given a 0-indexed string s and two patterns a and b, along with an integer k, find all starting indices i in s such that:

  • s[i..(i + a.length - 1)] matches a.
  • There exists an index j where s[j..(j + b.length - 1)] matches b and |i - j| <= k. Return the beautiful indices in sorted order.

Key Insights

  • Precompute all starting indices in s where substring a appears.
  • Precompute all starting indices in s where substring b appears.
  • Both lists are naturally sorted by the order of appearance.
  • For each index from the first list, use binary search on the second list to check if any index j exists with |i - j| <= k.
  • This transforms the problem into efficiently querying ranges in a sorted list.

Space and Time Complexity

Time Complexity: O(n + m log m), where n is the length of s (for the two scans) and m is the number of occurrences of pattern b (used in binary search for each occurrence of a). Space Complexity: O(n) for storing the indices.

Solution

We first scan through s to collect all starting indices where the substring equals a and similarly for b. Then, for each index i in the a-occurrences, we perform a binary search on the sorted list of b-occurrences to find the smallest index j such that j is at least (i - k). We then check if the found j (or its predecessor) satisfies |i - j| <= k. This binary search step reduces the time required compared to a brute-force comparison, making the solution efficient even for large inputs.

Code Solutions

import bisect

def find_beautiful_indices(s, a, b, k):
    # Precompute indices where substring a appears
    indices_a = []
    indices_b = []
    n = len(s)
    len_a = len(a)
    len_b = len(b)
    for i in range(n - len_a + 1):
        if s[i:i+len_a] == a:
            indices_a.append(i)
    # Precompute indices where substring b appears
    for j in range(n - len_b + 1):
        if s[j:j+len_b] == b:
            indices_b.append(j)
    
    beautiful = []
    # For each index in indices_a, check if an occurrence of b exists within distance k using binary search
    for i in indices_a:
        # Find the leftmost index in indices_b with value >= i - k
        l = bisect.bisect_left(indices_b, i - k)
        if l < len(indices_b) and abs(indices_b[l] - i) <= k:
            beautiful.append(i)
        elif l - 1 >= 0 and abs(indices_b[l-1] - i) <= k:
            beautiful.append(i)
    return beautiful

# Example usage:
if __name__ == "__main__":
    s = "isawsquirrelnearmysquirrelhouseohmy"
    a = "my"
    b = "squirrel"
    k = 15
    print(find_beautiful_indices(s, a, b, k))  # Expected output: [16, 33]
← Back to All Questions