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 I

Difficulty: Medium

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:

  1. 0 <= i <= s.length - a.length
  2. s[i..(i + a.length - 1)] == a
  3. 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 requires identifying indices in a string where a specific substring appears, while also checking for the proximity of another substring within a defined range.
  • The constraints allow for efficient substring searching and checks within the given bounds.
  • Utilizing two-pointer techniques can simplify the process of checking the proximity condition for indices.

Space and Time Complexity

Time Complexity: O(n * (a.length + b.length)), where n is the length of the string s. In the worst case, we may need to check each index for the presence of substrings a and b.

Space Complexity: O(m + p), where m is the number of occurrences of substring a and p is the number of occurrences of substring b captured in lists.

Solution

To solve the problem, we will:

  1. Iterate through the string s and find all starting indices where the substring a occurs.
  2. Similarly, find all starting indices where the substring b occurs.
  3. For each index found for a, check if there exists any index found for b such that the absolute difference between the two indices is less than or equal to k.
  4. Collect all valid indices for a that meet the proximity condition and return them sorted.

Data structures used:

  • Lists to store the indices of occurrences of substrings a and b.
  • Two pointers (or simple iteration) to efficiently check proximity.

Code Solutions

def find_beautiful_indices(s, a, b, k):
    a_indices = []
    b_indices = []
    
    # Find all indices for substring a
    for i in range(len(s) - len(a) + 1):
        if s[i:i + len(a)] == a:
            a_indices.append(i)
    
    # Find all indices for substring b
    for j in range(len(s) - len(b) + 1):
        if s[j:j + len(b)] == b:
            b_indices.append(j)
    
    beautiful_indices = []
    
    # Check for beautiful indices
    for i in a_indices:
        for j in b_indices:
            if abs(j - i) <= k:
                beautiful_indices.append(i)
                break
    
    return sorted(set(beautiful_indices))
← Back to All Questions