Find Beautiful Indices in the Given Array I

Medium

Palantir

26 views

Topics:

ArraysTwo PointersStrings

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.

Example 1:

Input: s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15
Output: [16,33]
Explanation: There are 2 beautiful indices: [16,33].
- The index 16 is beautiful as s[16..17] == "my" and there exists an index 4 with s[4..11] == "squirrel" and |16 - 4| <= 15.
- The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 - 18| <= 15.
Thus we return [16,33] as the result.

Example 2:

Input: s = "abcd", a = "a", b = "a", k = 4
Output: [0]
Explanation: There is 1 beautiful index: [0].
- The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 - 0| <= 4.
Thus we return [0] as the result.

Constraints:

1 <= k <= s.length <= 10⁵
1 <= a.length, b.length <= 10
s, a, and b contain only lowercase English letters.

Try coding it in LeetCode

Find Beautiful Indices in the Given Array I

Medium

Palantir

26 views

Topics:

ArraysTwo PointersStrings

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.

Example 1:

Input: s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15
Output: [16,33]
Explanation: There are 2 beautiful indices: [16,33].
- The index 16 is beautiful as s[16..17] == "my" and there exists an index 4 with s[4..11] == "squirrel" and |16 - 4| <= 15.
- The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 - 18| <= 15.
Thus we return [16,33] as the result.

Example 2:

Input: s = "abcd", a = "a", b = "a", k = 4
Output: [0]
Explanation: There is 1 beautiful index: [0].
- The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 - 0| <= 4.
Thus we return [0] as the result.

Constraints:

1 <= k <= s.length <= 10⁵
1 <= a.length, b.length <= 10
s, a, and b contain only lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum lengths of strings s, a, and b? What is the maximum value of k?
Can strings a and b be empty strings or null? What should I return in those cases?
If multiple indices i are beautiful, should they be returned in ascending order without duplicates?
Is it possible for the same index in 's' to be a match for both 'a' and 'b'?
What should I return if no beautiful indices are found?

Brute Force Solution

Approach

The brute force method for this problem involves examining every possible position to see if it meets the criteria. We will check each spot to see if it can be part of the final answer. Because this is brute force, we won't be clever, just thorough.

Here's how the algorithm would work step-by-step:

For every position in the main sequence of items, consider it as a potential starting point.
For each of these potential starting points, look everywhere in the sequence to see if the distance to a matching item is acceptable.
If the distance is acceptable, remember this original position as a 'beautiful' position.
After checking every single position against every other position, report the 'beautiful' positions that were found.

Code Implementation

def find_beautiful_indices_brute_force(main_string, substring_one, substring_two, maximum_difference):
    beautiful_indices = []

    for first_string_index in range(len(main_string)):
        # Consider each index as a potential beautiful index

        is_beautiful = False
        for second_string_index in range(len(main_string)):
            # Search for matches to the second string

            if main_string[second_string_index:second_string_index + len(substring_two)] == substring_two:
                # Check the distance between indices

                if abs(first_string_index - second_string_index) <= maximum_difference:
                    # Mark as beautiful and stop checking

                    is_beautiful = True

                    break

        if is_beautiful and main_string[first_string_index:first_string_index + len(substring_one)] == substring_one:
            # Add the index to result if its beautiful

            beautiful_indices.append(first_string_index)

    return beautiful_indices

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n indices in the first string, considering each as a potential beautiful index. For each of these n indices, it iterates through all n indices of the second string to find matches and check the distance condition. Thus, we have a nested loop structure where the outer loop runs n times and the inner loop also runs n times. Therefore, the total number of operations is proportional to n * n, which simplifies to O(n²).

Space Complexity

O(N) – The brute force approach, as described, only requires storing 'beautiful' positions that were found. In the worst case, every single position in the input array `s` (of size N) could be a beautiful index. Therefore, we would need to store all N indices in a list to hold the result. This temporary list contributes to the auxiliary space used. The space complexity is thus O(N), where N is the length of the input array s.

Optimal Solution

Approach

The efficient solution identifies matches by pre-processing the text. It then uses this information to quickly check the distance between matches instead of re-searching every time.

Here's how the algorithm would work step-by-step:

First, find all places where the first word appears in the big block of text.
Then, separately, find all places where the second word appears in the big block of text.
Now, for each place where the first word appears, check if there's a place where the second word appears nearby, within the allowed distance.
If there is a nearby match, save the location of the first word.
At the end, provide the saved locations of the first word where a nearby second word was found.

Code Implementation

def find_beautiful_indices(text, word1, word2, allowed_distance):
    first_word_indices = []
    second_word_indices = []
    beautiful_indices = []

    # Find all starting indices of word1 in text.
    for index in range(len(text) - len(word1) + 1):
        if text[index:index + len(word1)] == word1:
            first_word_indices.append(index)

    # Find all starting indices of word2 in text.
    for index in range(len(text) - len(word2) + 1):
        if text[index:index + len(word2)] == word2:
            second_word_indices.append(index)

    # Iterate through the indices of the first word.
    for first_word_index in first_word_indices:
        # Check if any index of the second word is within the allowed distance.
        for second_word_index in second_word_indices:
            if abs(first_word_index - second_word_index) <= allowed_distance:
                # Add the index to the result if it's beautiful.
                beautiful_indices.append(first_word_index)
                break # Optimization: Once found, no need to check others.

    return sorted(beautiful_indices)

Big(O) Analysis

Time Complexity

O(n*m + n*k) – Finding all occurrences of the first word involves scanning the text of length n, potentially using string matching algorithms of complexity O(m) where m is the length of the first word. Similarly, finding all occurrences of the second word also takes O(k) time per character in the text, where k is the length of the second word. The time it takes to search through the entire document for occurrences of the two words then becomes O(n*m + n*k). Finally, iterating through the first word's indices and comparing the distances to the second word's indices is proportional to the number of occurrences times the maximum distance allowed, this is bounded by n. Since we perform this distance check for each index of the first word, its cost will be no more than O(n).

Space Complexity

O(N) – The space complexity is determined by the storage of the indices where the first and second words appear in the text. In the worst-case scenario, both the lists containing indices of the first word and the second word could potentially store all the indices of the text if those words appear at every position. This would require space proportional to the length of the input text, N. Therefore, the auxiliary space used is O(N).

Edge Cases

Case	How to Handle
s is null or empty	Return an empty list if s is null or empty as no indices can be found.
a is null or empty	Return an empty list if a is null or empty as no indices for 'a' can be found.
b is null or empty	Return an empty list if b is null or empty as no indices for 'b' can be found.
k is zero	The algorithm must find indices i and j that are exactly the same; iterate through a_indices and check if it exists in b_indices.
a or b is longer than s	Return an empty list because the substrings 'a' or 'b' cannot be found in s.
s, a, and b are identical and k is small	Ensure all indices are marked as beautiful since \|i-j\| <= k always holds for close indices.
Large input string s	Ensure the solution has reasonable time complexity (e.g., O(n*m) where n is the length of s and m is the length of a and b) by using string searching algorithms efficiently.
No beautiful indices exist	The solution should return an empty sorted list when no indices i and j satisfy the condition \|i - j\| <= k.