#3008

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find Beautiful Indices in the Given Array II

Find Beautiful Indices in the Given Array II challenges you to use binary search and string matching techniques.

two pointers string binary search rolling hash string matching

Problem Statement

You are given a string s, two substrings a and b, and an integer k. An index i is considered beautiful if the substring s[i..i+len(a)-1] == a, and there exists another index j such that s[j..j+len(b)-1] == b and the absolute difference between i and j is less than or equal to k.

Return a sorted array of beautiful indices. The challenge requires efficient processing of the string using binary search to optimize the valid index search. With constraints that allow s and a to be very large, you'll need to use advanced string matching techniques like KMP or rolling hashes to solve the problem efficiently.

Examples

Example 1

Input: s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15

Output: [16,33]

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]

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 <= 5 * 105
1 <= a.length, b.length <= 5 * 105
s, a, and b contain only lowercase English letters.

Solution Approach

Binary Search Optimization

The key to solving this problem efficiently lies in binary searching the valid index space. Once we find the positions of a in s, we can binary search to find where b can exist such that the absolute index difference is within the allowed range k.

String Matching with KMP or Rolling Hash

Use KMP or rolling hash to efficiently locate occurrences of a and b in the string s. These techniques allow you to avoid rechecking the string repeatedly and reduce time complexity from brute force searching.

Handling Large Inputs

Given the input constraints, a direct approach could lead to timeouts. You must combine binary search and string matching to optimize both time and space. This will allow you to handle the largest possible strings efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on the efficiency of the string matching technique and the binary search operations. With a well-optimized approach, the time complexity is approximately O(n log n), where n is the length of the string s. The space complexity depends on the method used for string matching, typically O(n).

What Interviewers Usually Probe

The candidate effectively uses binary search and string matching techniques.
The candidate demonstrates an understanding of how to optimize search space in large datasets.
The candidate chooses an efficient string matching algorithm based on input size constraints.

Common Pitfalls or Variants

Common pitfalls

Not using binary search properly, leading to an inefficient solution.
Choosing a naive string matching approach, causing timeouts for large inputs.
Failing to consider edge cases where no beautiful indices exist, which could lead to incorrect results.

Follow-up variants

Consider variations where k is very large, and the efficiency of the algorithm is tested.
Extend the problem to handle multiple patterns for a and b.
Implement a solution that returns all beautiful indices within a given range instead of sorting them.

FAQ

How can I optimize the solution for the Find Beautiful Indices in the Given Array II problem?

The key optimization is using binary search over the index space, combined with efficient string matching algorithms like KMP or rolling hashes.

What is the time complexity of solving Find Beautiful Indices in the Given Array II?

The time complexity depends on the combination of binary search and string matching. It is typically O(n log n) for optimal solutions.

What techniques are most effective for string matching in this problem?

KMP and rolling hash are effective techniques for locating the substrings a and b within s, ensuring time efficiency.

How does the binary search play a role in solving this problem?

Binary search helps optimize the search space for beautiful indices, reducing the number of checks needed to verify the valid indices.

What are some edge cases I should consider for this problem?

Edge cases include scenarios where no beautiful indices exist, or where k is too small to allow for any valid index pairs.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        def build_prefix_function(pattern):
            prefix_function = [0] * len(pattern)
            j = 0
            for i in range(1, len(pattern)):
                while j > 0 and pattern[i] != pattern[j]:
                    j = prefix_function[j - 1]
                if pattern[i] == pattern[j]:
                    j += 1
                prefix_function[i] = j
            return prefix_function

        def kmp_search(pattern, text, prefix_function):
            occurrences = []
            j = 0
            for i in range(len(text)):
                while j > 0 and text[i] != pattern[j]:
                    j = prefix_function[j - 1]
                if text[i] == pattern[j]:
                    j += 1
                if j == len(pattern):
                    occurrences.append(i - j + 1)
                    j = prefix_function[j - 1]
            return occurrences

        prefix_a = build_prefix_function(a)
        prefix_b = build_prefix_function(b)

        resa = kmp_search(a, s, prefix_a)
        resb = kmp_search(b, s, prefix_b)

        res = []
        print(resa, resb)
        i = 0
        j = 0
        while i < len(resa):
            while j < len(resb):
                if abs(resb[j] - resa[i]) <= k:
                    res.append(resa[i])
                    break
                elif j + 1 < len(resb) and abs(resb[j + 1] - resa[i]) < abs(
                    resb[j] - resa[i]
                ):
                    j += 1
                else:
                    break
            i += 1
        return res

Continue Practicing

#3006 find beautiful indices in the given array i #3291 minimum number of valid strings to form target i #3292 minimum number of valid strings to form target ii