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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Beautiful Indices in the Given Array II

Difficulty: Hard

Problem Description

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.

Key Insights

  • The problem involves finding specific substrings (a and b) within a larger string (s).
  • The indices of the found substrings must satisfy a distance constraint defined by k.
  • Efficient substring search techniques are crucial due to the potential length of the input, which can be up to 500,000 characters.
  • Two-pointer or sliding window techniques may be beneficial to maintain the distance condition.

Space and Time Complexity

Time Complexity: O(n + m + p), where n is the length of s, m is the length of a, and p is the length of b.
Space Complexity: O(n + m + p) for storing the indices of substrings.

Solution

To solve the problem, we can use the following approach:

  1. Traverse the string s to find all occurrences of the substring a and store their indices.
  2. Similarly, traverse the string s to find all occurrences of the substring b and store their indices.
  3. For each index of a, check if there exists any index of b such that the absolute difference between their indices is less than or equal to k.
  4. Collect all valid indices of a that meet the criteria and return them in sorted order.

We can utilize two pointers to efficiently check the proximity condition for each found index.

Code Solutions

def find_beautiful_indices(s: str, a: str, b: str, k: int) -> list:
    n, m, p = len(s), len(a), len(b)
    indices_a = []
    indices_b = []
    
    # Find all occurrences of a
    for i in range(n - m + 1):
        if s[i:i + m] == a:
            indices_a.append(i)
    
    # Find all occurrences of b
    for j in range(n - p + 1):
        if s[j:j + p] == b:
            indices_b.append(j)

    beautiful_indices = []
    j = 0
    for i in indices_a:
        while j < len(indices_b) and indices_b[j] < i - k:
            j += 1
        if j < len(indices_b) and abs(indices_b[j] - i) <= k:
            beautiful_indices.append(i)

    return beautiful_indices
← Back to All Questions