#3006

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find Beautiful Indices in the Given Array I

Identify all beautiful indices where substring a appears and a nearby substring b exists within distance k efficiently.

two pointers string binary search rolling hash string matching

Problem Statement

Given a 0-indexed string s, a string a, a string b, and an integer k, determine which indices in s are beautiful.

An index i is considered beautiful if the substring starting at i matches a and there exists an index j such that the substring starting at j matches b, with the absolute difference |i - j| not exceeding k. Return the sorted list of all beautiful indices.

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

Solution Approach

Precompute substring matches

Scan the string s to record all starting indices where substring a and substring b occur. This prepares for efficient distance checks without repeated string comparisons.

Check distances with binary search

For each index i where a occurs, use binary search on the list of b indices to determine if any are within k distance. This leverages the pattern of searching over a valid answer space for speed.

Optimize substring checks

Use rolling hash or string hashing to compare substrings in constant time, reducing unnecessary comparisons and ensuring the solution scales to the maximum s length.

Complexity Analysis

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

Time complexity is O(len(s) * log(number_of_b_indices)) using binary search for each a occurrence. Space complexity is O(len(s)) to store indices of a and b occurrences. Rolling hash adds minimal extra space for hashes.

What Interviewers Usually Probe

Looking for understanding of binary search over the answer space.
Checks if you notice distance constraints between a and b occurrences.
Observes whether you optimize substring matching to avoid repeated scanning.

Common Pitfalls or Variants

Common pitfalls

Not handling overlapping substrings correctly.
Iterating over all pairs of a and b indices without binary search, causing TLE.
Ignoring distance k constraint or miscalculating absolute difference.

Follow-up variants

Find beautiful indices where multiple substrings b can satisfy the distance condition.
Change the problem to count the number of beautiful indices instead of listing them.
Extend to 2D grids where 'beautiful' positions depend on nearby matching patterns.

FAQ

What defines a beautiful index in this problem?

A beautiful index i is where substring a starts and there exists a substring b within absolute distance k.

Can I use brute force to find all beautiful indices?

Brute force works for small strings but fails for s up to 10^5; using binary search over b indices is essential.

How does the binary search pattern apply here?

Binary search checks efficiently if a b index exists within distance k from each a index, matching the valid answer space pattern.

Is rolling hash necessary for this problem?

Not strictly, but it optimizes substring comparisons to constant time and avoids repeated scans.

What if multiple b occurrences satisfy the distance k?

Any occurrence within k distance makes the index i beautiful; return i once in the sorted list.

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

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