3006. Find Beautiful Indices in the Given Array I

MediumTwo PointersStringBinary SearchString MatchingHash FunctionRolling Hash

Problem Description

You are given a string s and need to find all "beautiful" indices in it. An index i is considered beautiful if it meets specific conditions involving two pattern strings a and b, and a distance constraint k.

For an index i to be beautiful, three conditions must be satisfied:

Valid position for pattern a: The index i must be positioned such that pattern a can fit starting from i. This means 0 <= i <= s.length - a.length.
Pattern a matches: The substring of s starting at index i with length equal to a.length must exactly match pattern a. In other words, s[i..(i + a.length - 1)] == a.
Pattern b exists nearby: There must exist at least one index j where:
- Pattern b can fit starting from j: 0 <= j <= s.length - b.length
- The substring matches pattern b: s[j..(j + b.length - 1)] == b
- The distance between i and j is at most k: |j - i| <= k

The task is to find all beautiful indices and return them in a sorted array from smallest to largest.

Example: If s = "isawsquirrelnearsquirrelk", a = "squirrel", b = "k", and k = 15, then index 4 would be beautiful because:

Pattern "squirrel" appears at index 4
Pattern "k" appears at index 24
The distance |24 - 4| = 20 is greater than 15, so we'd need to check other occurrences

The solution uses the KMP (Knuth-Morris-Pratt) algorithm to efficiently find all occurrences of patterns a and b in string s, then checks which occurrences of a have at least one occurrence of b within distance k.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The core challenge is to efficiently find all occurrences of two patterns a and b in string s, then determine which occurrences of a have at least one occurrence of b within distance k.

A naive approach would involve checking every possible position in s for pattern a, and for each match, checking if pattern b exists within the distance constraint. This would result in O(n * m * p) time complexity where n is the length of s, m is the length of a, and p is the length of b, which is inefficient for large strings.

The key insight is to separate the problem into two independent pattern-matching tasks first, then combine the results. We can:

Find all positions where pattern a occurs in s
Find all positions where pattern b occurs in s
Check which positions from step 1 have at least one position from step 2 within distance k

For efficient pattern matching, the KMP algorithm is ideal because it can find all occurrences of a pattern in O(n + m) time, where n is the text length and m is the pattern length. KMP achieves this efficiency by preprocessing the pattern to build a prefix function that helps skip unnecessary comparisons.

Once we have two sorted lists of indices (one for a occurrences and one for b occurrences), we need to find which indices from the first list have at least one index from the second list within distance k. Since both lists are sorted, we can use a two-pointer technique to efficiently check this condition without repeatedly scanning the entire second list for each element in the first list.

The two-pointer approach works by maintaining pointers i and j for the two lists. For each occurrence of a at position resa[i], we advance j through resb to find if any resb[j] satisfies |resb[j] - resa[i]| <= k. The optimization comes from not resetting j to 0 for each new i, since if resb[j] is too far from resa[i], it might still be close enough to resa[i+1].

Learn more about Two Pointers and Binary Search patterns.

Solution Approach

The solution implements the KMP (Knuth-Morris-Pratt) algorithm for pattern matching, followed by a two-pointer technique to find beautiful indices.

Step 1: Building the Prefix Function

The build_prefix_function creates an array that stores the length of the longest proper prefix that is also a suffix for each position in the pattern. This preprocessing step is crucial for KMP's efficiency.

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

For each position i, we maintain j as the length of the current matching prefix. When characters don't match, we use the prefix function to jump back to a previous position where we might continue matching.

Step 2: KMP Search

The kmp_search function finds all occurrences of a pattern in the text using the 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]

When we find a complete match (j == len(pattern)), we record the starting position i - j + 1 and continue searching for overlapping occurrences.

Step 3: Finding All Occurrences

We apply KMP to find all occurrences of both patterns:

resa = kmp_search(a, s, prefix_a) - all positions where pattern a occurs
resb = kmp_search(b, s, prefix_b) - all positions where pattern b occurs

Both lists are naturally sorted since we scan the string from left to right.

Step 4: Identifying Beautiful Indices

The final step uses a two-pointer approach to find which occurrences of a have at least one occurrence of b within distance k:

res = []
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

For each position resa[i], we advance j through resb to find a matching position within distance k. The optimization checks if the next element in resb would be closer to resa[i] before stopping the search. Once we find a valid j for resa[i], we add resa[i] to the result and move to the next i.

Time Complexity: O(n + m + p) where n = len(s), m = len(a), p = len(b) for the KMP searches, plus O(x + y) for the two-pointer merge where x and y are the number of occurrences of patterns a and b respectively.

Space Complexity: O(m + p + x + y) for storing the prefix functions and occurrence lists.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

s = "ababcab"
a = "ab"
b = "ab"
k = 2

Step 1: Build Prefix Functions

For pattern a = "ab":

prefix_a[0] = 0 (no proper prefix for "a")
prefix_a[1] = 0 (no prefix of "ab" that's also a suffix)
Result: prefix_a = [0, 0]

For pattern b = "ab":

Same pattern, so prefix_b = [0, 0]

Step 2: Find All Occurrences Using KMP

Finding occurrences of a = "ab" in s = "ababcab":

Position 0: s[0:2] = "ab" ✓ matches
Position 2: s[2:4] = "ab" ✓ matches
Position 5: s[5:7] = "ab" ✓ matches
Result: resa = [0, 2, 5]

Finding occurrences of b = "ab" in s = "ababcab":

Same pattern, so resb = [0, 2, 5]

Step 3: Find Beautiful Indices Using Two Pointers

Now we check which indices in resa have at least one index in resb within distance k = 2:

Check resa[0] = 0:
- resb[0] = 0: distance = |0 - 0| = 0 ≤ 2 ✓
- Index 0 is beautiful!
Check resa[1] = 2:
- Start checking from resb[0] = 0: distance = |0 - 2| = 2 ≤ 2 ✓
- Index 2 is beautiful!
Check resa[2] = 5:
- resb[0] = 0: distance = |0 - 5| = 5 > 2 ✗
- resb[1] = 2: distance = |2 - 5| = 3 > 2 ✗
- resb[2] = 5: distance = |5 - 5| = 0 ≤ 2 ✓
- Index 5 is beautiful!

Final Result: [0, 2, 5]

All three positions where pattern a appears are beautiful because each has at least one occurrence of pattern b within distance 2.

Solution Implementation

1class Solution:
2    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
3        """
4        Find all beautiful indices in string s.
5        A beautiful index i is where:
6        1. s[i:i+len(a)] == a
7        2. There exists j where s[j:j+len(b)] == b and |i-j| <= k
8        """
9      
10        def build_prefix_function(pattern: str) -> List[int]:
11            """
12            Build the prefix function (failure function) for KMP algorithm.
13            prefix_function[i] = length of longest proper prefix of pattern[0:i+1]
14            that is also a suffix of pattern[0:i+1]
15            """
16            prefix_function = [0] * len(pattern)
17            j = 0  # Length of the current matching prefix
18          
19            for i in range(1, len(pattern)):
20                # If characters don't match, fallback using prefix function
21                while j > 0 and pattern[i] != pattern[j]:
22                    j = prefix_function[j - 1]
23              
24                # If characters match, extend the matching prefix
25                if pattern[i] == pattern[j]:
26                    j += 1
27                  
28                prefix_function[i] = j
29          
30            return prefix_function
31
32        def kmp_search(pattern: str, text: str, prefix_function: List[int]) -> List[int]:
33            """
34            Find all occurrences of pattern in text using KMP algorithm.
35            Returns list of starting indices where pattern is found.
36            """
37            occurrences = []
38            j = 0  # Current position in pattern
39          
40            for i in range(len(text)):
41                # If mismatch, use prefix function to skip comparisons
42                while j > 0 and text[i] != pattern[j]:
43                    j = prefix_function[j - 1]
44              
45                # If characters match, move to next character in pattern
46                if text[i] == pattern[j]:
47                    j += 1
48              
49                # If complete pattern is matched
50                if j == len(pattern):
51                    occurrences.append(i - j + 1)  # Add starting index
52                    j = prefix_function[j - 1]  # Continue searching for more occurrences
53          
54            return occurrences
55
56        # Build prefix functions for both patterns
57        prefix_a = build_prefix_function(a)
58        prefix_b = build_prefix_function(b)
59
60        # Find all occurrences of pattern a and b in string s
61        indices_a = kmp_search(a, s, prefix_a)
62        indices_b = kmp_search(b, s, prefix_b)
63
64        # Find beautiful indices
65        beautiful_indices = []
66        i = 0  # Pointer for indices_a
67        j = 0  # Pointer for indices_b
68      
69        # For each occurrence of pattern a
70        while i < len(indices_a):
71            # Try to find a matching occurrence of pattern b within distance k
72            while j < len(indices_b):
73                # If current b index is within distance k from current a index
74                if abs(indices_b[j] - indices_a[i]) <= k:
75                    beautiful_indices.append(indices_a[i])
76                    break
77                # If next b index would be closer to current a index, move to it
78                elif j + 1 < len(indices_b) and abs(indices_b[j + 1] - indices_a[i]) < abs(indices_b[j] - indices_a[i]):
79                    j += 1
80                else:
81                    break
82            i += 1
83      
84        return beautiful_indices
85

1public class Solution {
2    /**
3     * Computes the Longest Proper Prefix which is also Suffix (LPS) array
4     * for the KMP pattern matching algorithm
5     * @param pattern The pattern string to compute LPS for
6     * @param lps The array to store LPS values
7     */
8    public void computeLPS(String pattern, int[] lps) {
9        int patternLength = pattern.length();
10        int lengthOfPreviousLPS = 0; // Length of the previous longest prefix suffix
11      
12        lps[0] = 0; // LPS of first character is always 0
13      
14        int currentIndex = 1;
15        while (currentIndex < patternLength) {
16            // If characters match, extend the current LPS
17            if (pattern.charAt(currentIndex) == pattern.charAt(lengthOfPreviousLPS)) {
18                lengthOfPreviousLPS++;
19                lps[currentIndex] = lengthOfPreviousLPS;
20                currentIndex++;
21            } else {
22                // If characters don't match
23                if (lengthOfPreviousLPS != 0) {
24                    // Use previously computed LPS to avoid redundant comparisons
25                    lengthOfPreviousLPS = lps[lengthOfPreviousLPS - 1];
26                } else {
27                    // No proper prefix found, set LPS to 0
28                    lps[currentIndex] = 0;
29                    currentIndex++;
30                }
31            }
32        }
33    }
34  
35    /**
36     * KMP (Knuth-Morris-Pratt) algorithm to find all occurrences of pattern in text
37     * @param pat The pattern to search for
38     * @param txt The text to search in
39     * @return List of starting indices where pattern is found in text
40     */
41    public List<Integer> KMP_codestorywithMIK(String pat, String txt) {
42        int textLength = txt.length();
43        int patternLength = pat.length();
44        List<Integer> matchIndices = new ArrayList<>();
45      
46        // Compute LPS array for the pattern
47        int[] lps = new int[patternLength];
48        computeLPS(pat, lps);
49      
50        int textIndex = 0;    // Index for traversing the text
51        int patternIndex = 0; // Index for traversing the pattern
52      
53        while (textIndex < textLength) {
54            // Characters match, move both pointers forward
55            if (pat.charAt(patternIndex) == txt.charAt(textIndex)) {
56                textIndex++;
57                patternIndex++;
58            }
59          
60            // Complete pattern found
61            if (patternIndex == patternLength) {
62                matchIndices.add(textIndex - patternIndex); // Add starting index of match
63                patternIndex = lps[patternIndex - 1]; // Continue searching for more occurrences
64            } 
65            // Mismatch after some matches
66            else if (textIndex < textLength && pat.charAt(patternIndex) != txt.charAt(textIndex)) {
67                if (patternIndex != 0) {
68                    // Use LPS to skip unnecessary comparisons
69                    patternIndex = lps[patternIndex - 1];
70                } else {
71                    // No matches, move to next character in text
72                    textIndex++;
73                }
74            }
75        }
76      
77        return matchIndices;
78    }
79  
80    /**
81     * Binary search to find the first index in sorted list where value >= target
82     * @param list The sorted list to search in
83     * @param target The target value to find lower bound for
84     * @return Index of first element >= target, or list.size() if all elements < target
85     */
86    private int lowerBound(List<Integer> list, int target) {
87        int left = 0;
88        int right = list.size() - 1;
89        int result = list.size(); // Default to list size if no element >= target
90      
91        while (left <= right) {
92            int mid = left + (right - left) / 2;
93          
94            if (list.get(mid) >= target) {
95                // Found a candidate, try to find a smaller index
96                result = mid;
97                right = mid - 1;
98            } else {
99                // Current element is too small, search right half
100                left = mid + 1;
101            }
102        }
103      
104        return result;
105    }
106  
107    /**
108     * Finds beautiful indices in string s where pattern a occurs and pattern b occurs within distance k
109     * @param s The input string
110     * @param a The first pattern to search for
111     * @param b The second pattern to search for
112     * @param k The maximum distance between occurrences of a and b
113     * @return List of beautiful indices (starting positions of pattern a)
114     */
115    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
116        int stringLength = s.length();
117      
118        // Find all occurrences of pattern a in string s
119        List<Integer> aIndices = KMP_codestorywithMIK(a, s);
120        // Find all occurrences of pattern b in string s
121        List<Integer> bIndices = KMP_codestorywithMIK(b, s);
122      
123        List<Integer> beautifulIndicesList = new ArrayList<>();
124      
125        // For each occurrence of pattern a
126        for (int aIndex : aIndices) {
127            // Calculate the valid range for pattern b occurrences
128            int leftLimit = Math.max(0, aIndex - k);              // Ensure within bounds
129            int rightLimit = Math.min(stringLength - 1, aIndex + k); // Ensure within bounds
130          
131            // Find the first occurrence of b that is >= leftLimit
132            int lowerBoundIndex = lowerBound(bIndices, leftLimit);
133          
134            // Check if there exists a valid b occurrence within the range
135            if (lowerBoundIndex < bIndices.size() && 
136                bIndices.get(lowerBoundIndex) <= rightLimit) {
137                beautifulIndicesList.add(aIndex);
138            }
139        }
140      
141        return beautifulIndicesList;
142    }
143}
144

1class Solution {
2public:
3    vector<int> beautifulIndices(string s, string patternA, string patternB, int k) {
4        // Find all occurrences of patternA and patternB in string s using KMP algorithm
5        vector<int> indicesA = kmpSearch(s, patternA);
6        vector<int> indicesB = kmpSearch(s, patternB);
7      
8        // Sort indicesB for binary search (though KMP already returns sorted indices)
9        sort(indicesB.begin(), indicesB.end());
10      
11        vector<int> result;
12      
13        // For each occurrence of patternA, check if there exists a valid patternB within distance k
14        for (int idxA : indicesA) {
15            // Find the range of indices in indicesB that could satisfy |j - i| <= k
16            // Lower bound: first index >= (idxA - k)
17            int leftPos = lower_bound(indicesB.begin(), indicesB.end(), idxA - k) - indicesB.begin();
18            // Upper bound: first index >= (idxA + k + 1), we use patternB.length() but should be just k + 1
19            int rightPos = upper_bound(indicesB.begin(), indicesB.end(), idxA + k) - indicesB.begin();
20          
21            // Check if any index in the range satisfies the distance constraint
22            bool found = false;
23            for (int i = leftPos; i < rightPos; i++) {
24                if (abs(indicesB[i] - idxA) <= k) {
25                    result.push_back(idxA);
26                    found = true;
27                    break;
28                }
29            }
30        }
31      
32        return result;
33    }
34
35private:
36    // KMP pattern matching algorithm to find all occurrences of pattern in text
37    vector<int> kmpSearch(string text, string pattern) {
38        vector<int> occurrences;
39      
40        // Build the prefix function (failure function) for the pattern
41        vector<int> prefixTable = computePrefixFunction(pattern);
42      
43        int matchedChars = 0;  // Number of characters matched so far
44      
45        // Scan through the text
46        for (int i = 0; i < text.length(); i++) {
47            // While there's a mismatch, use prefix table to skip comparisons
48            while (matchedChars > 0 && pattern[matchedChars] != text[i]) {
49                matchedChars = prefixTable[matchedChars - 1];
50            }
51          
52            // If current characters match, increment matched count
53            if (pattern[matchedChars] == text[i]) {
54                matchedChars++;
55            }
56          
57            // If entire pattern is matched, record the starting position
58            if (matchedChars == pattern.length()) {
59                occurrences.push_back(i - matchedChars + 1);
60                // Continue searching for overlapping matches
61                matchedChars = prefixTable[matchedChars - 1];
62            }
63        }
64      
65        return occurrences;
66    }
67  
68    // Compute the prefix function (failure function) for KMP algorithm
69    vector<int> computePrefixFunction(string pattern) {
70        int patternLength = pattern.length();
71        vector<int> prefixTable(patternLength, 0);
72      
73        int prefixLength = 0;  // Length of the current proper prefix which is also a suffix
74      
75        // Build the prefix table
76        for (int i = 1; i < patternLength; i++) {
77            // Find the longest proper prefix which is also a suffix
78            while (prefixLength > 0 && pattern[prefixLength] != pattern[i]) {
79                prefixLength = prefixTable[prefixLength - 1];
80            }
81          
82            // If characters match, extend the prefix
83            if (pattern[prefixLength] == pattern[i]) {
84                prefixLength++;
85            }
86          
87            // Store the length of longest proper prefix for current position
88            prefixTable[i] = prefixLength;
89        }
90      
91        return prefixTable;
92    }
93};
94

1/**
2 * Finds all beautiful indices in string s where patternA occurs
3 * A beautiful index i is where patternA occurs at position i and 
4 * there exists an occurrence of patternB at position j such that |j - i| <= k
5 */
6function beautifulIndices(s: string, patternA: string, patternB: string, k: number): number[] {
7    // Find all occurrences of patternA and patternB in string s using KMP algorithm
8    const indicesA: number[] = kmpSearch(s, patternA);
9    const indicesB: number[] = kmpSearch(s, patternB);
10  
11    // Sort indicesB for binary search (though KMP already returns sorted indices)
12    indicesB.sort((a, b) => a - b);
13  
14    const result: number[] = [];
15  
16    // For each occurrence of patternA, check if there exists a valid patternB within distance k
17    for (const idxA of indicesA) {
18        // Find the range of indices in indicesB that could satisfy |j - i| <= k
19        // Lower bound: first index >= (idxA - k)
20        const leftPos = lowerBound(indicesB, idxA - k);
21        // Upper bound: first index > (idxA + k)
22        const rightPos = upperBound(indicesB, idxA + k);
23      
24        // Check if any index in the range satisfies the distance constraint
25        let found = false;
26        for (let i = leftPos; i < rightPos; i++) {
27            if (Math.abs(indicesB[i] - idxA) <= k) {
28                result.push(idxA);
29                found = true;
30                break;
31            }
32        }
33    }
34  
35    return result;
36}
37
38/**
39 * KMP pattern matching algorithm to find all occurrences of pattern in text
40 * Returns an array of starting indices where the pattern is found
41 */
42function kmpSearch(text: string, pattern: string): number[] {
43    const occurrences: number[] = [];
44  
45    // Build the prefix function (failure function) for the pattern
46    const prefixTable: number[] = computePrefixFunction(pattern);
47  
48    let matchedChars = 0;  // Number of characters matched so far
49  
50    // Scan through the text
51    for (let i = 0; i < text.length; i++) {
52        // While there's a mismatch, use prefix table to skip comparisons
53        while (matchedChars > 0 && pattern[matchedChars] !== text[i]) {
54            matchedChars = prefixTable[matchedChars - 1];
55        }
56      
57        // If current characters match, increment matched count
58        if (pattern[matchedChars] === text[i]) {
59            matchedChars++;
60        }
61      
62        // If entire pattern is matched, record the starting position
63        if (matchedChars === pattern.length) {
64            occurrences.push(i - matchedChars + 1);
65            // Continue searching for overlapping matches
66            matchedChars = prefixTable[matchedChars - 1];
67        }
68    }
69  
70    return occurrences;
71}
72
73/**
74 * Compute the prefix function (failure function) for KMP algorithm
75 * Returns an array where prefixTable[i] represents the length of the longest proper
76 * prefix of pattern[0..i] which is also a suffix of pattern[0..i]
77 */
78function computePrefixFunction(pattern: string): number[] {
79    const patternLength = pattern.length;
80    const prefixTable: number[] = new Array(patternLength).fill(0);
81  
82    let prefixLength = 0;  // Length of the current proper prefix which is also a suffix
83  
84    // Build the prefix table
85    for (let i = 1; i < patternLength; i++) {
86        // Find the longest proper prefix which is also a suffix
87        while (prefixLength > 0 && pattern[prefixLength] !== pattern[i]) {
88            prefixLength = prefixTable[prefixLength - 1];
89        }
90      
91        // If characters match, extend the prefix
92        if (pattern[prefixLength] === pattern[i]) {
93            prefixLength++;
94        }
95      
96        // Store the length of longest proper prefix for current position
97        prefixTable[i] = prefixLength;
98    }
99  
100    return prefixTable;
101}
102
103/**
104 * Binary search helper: finds the first index in sorted array where value >= target
105 * Returns the index where target should be inserted to maintain sorted order
106 */
107function lowerBound(arr: number[], target: number): number {
108    let left = 0;
109    let right = arr.length;
110  
111    while (left < right) {
112        const mid = Math.floor((left + right) / 2);
113        if (arr[mid] < target) {
114            left = mid + 1;
115        } else {
116            right = mid;
117        }
118    }
119  
120    return left;
121}
122
123/**
124 * Binary search helper: finds the first index in sorted array where value > target
125 * Returns the index where values greater than target begin
126 */
127function upperBound(arr: number[], target: number): number {
128    let left = 0;
129    let right = arr.length;
130  
131    while (left < right) {
132        const mid = Math.floor((left + right) / 2);
133        if (arr[mid] <= target) {
134            left = mid + 1;
135        } else {
136            right = mid;
137        }
138    }
139  
140    return left;
141}
142

Time and Space Complexity

Time Complexity: O(n + m*len(a) + m*len(b) + p*q) where:

n = len(s) (length of the main string)
m = len(s) (for KMP search iterations)
p = len(resa) (number of occurrences of pattern a)
q = len(resb) (number of occurrences of pattern b)

Breaking down the time complexity:

Building prefix function for pattern a: O(len(a))
Building prefix function for pattern b: O(len(b))
KMP search for pattern a in string s: O(n + len(a))
KMP search for pattern b in string s: O(n + len(b))
Finding beautiful indices with nested loops: O(p * q) in worst case

The overall time complexity simplifies to O(n + p*q) where the KMP searches dominate the prefix function building, and in the worst case where p and q could both be O(n), this becomes O(n²).

Space Complexity: O(len(a) + len(b) + p + q)

Breaking down the space complexity:

Prefix function array for pattern a: O(len(a))
Prefix function array for pattern b: O(len(b))
List resa storing occurrences of a: O(p)
List resb storing occurrences of b: O(q)
Result list res: O(p) in worst case
Other variables: O(1)

The total space complexity is O(len(a) + len(b) + p + q), which in the worst case could be O(n) if the patterns are small and occur frequently.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Two-Pointer Logic for Finding Beautiful Indices

The current two-pointer approach has a critical flaw. The pointer j for indices_b never resets or moves backward, which causes it to miss valid matches when multiple occurrences of pattern a need to check against the same occurrences of pattern b.

Example of the Problem:

s = "ababab", a = "ab", b = "ab", k = 2
indices_a = [0, 2, 4], indices_b = [0, 2, 4]
When checking indices_a[0] = 0, we find indices_b[0] = 0 is valid (distance 0 ≤ 2)
When checking indices_a[1] = 2, the pointer j is still at 0, but the code moves it forward to j = 1 then j = 2, finding indices_b[2] = 4 is valid
When checking indices_a[2] = 4, the pointer j is already at 2, but indices_b[1] = 2 (which is valid with distance 2) is behind the current j position and will never be checked

Solution: Instead of maintaining a single forward-moving pointer, we should check all occurrences of b that fall within the valid range [indices_a[i] - k, indices_a[i] + k] for each occurrence of a. We can use binary search for efficiency:

def find_beautiful_indices_corrected(indices_a, indices_b, k):
    beautiful_indices = []
  
    for a_idx in indices_a:
        # Binary search to find if any b index is within distance k
        left, right = a_idx - k, a_idx + k
      
        # Find leftmost b index >= left using binary search
        lo, hi = 0, len(indices_b) - 1
        found = False
      
        while lo <= hi:
            mid = (lo + hi) // 2
            if indices_b[mid] < left:
                lo = mid + 1
            elif indices_b[mid] > right:
                hi = mid - 1
            else:  # indices_b[mid] is within [left, right]
                found = True
                break
      
        if found:
            beautiful_indices.append(a_idx)
  
    return beautiful_indices

Pitfall 2: Edge Case with Empty Patterns

The KMP implementation doesn't handle edge cases where patterns a or b might be empty strings. While this might not be a concern based on problem constraints, it's worth validating:

Solution: Add validation at the beginning of the function:

if not a or not b or not s:
    return []
if len(a) > len(s) or len(b) > len(s):
    return []

Pitfall 3: Inefficient Distance Checking in Two-Pointer Approach

The condition abs(indices_b[j + 1] - indices_a[i]) < abs(indices_b[j] - indices_a[i]) doesn't guarantee optimal pointer movement. Since both arrays are sorted, we should leverage this property more effectively.

Improved Two-Pointer Solution:

def find_beautiful_indices_improved(indices_a, indices_b, k):
    beautiful_indices = []
    j = 0  # Pointer for indices_b
  
    for a_idx in indices_a:
        # Move j backward if we've gone too far ahead
        while j > 0 and indices_b[j] > a_idx + k:
            j -= 1
      
        # Move j forward to find the first b index in range
        while j < len(indices_b) and indices_b[j] < a_idx - k:
            j += 1
      
        # Check if current j is within range
        if j < len(indices_b) and abs(indices_b[j] - a_idx) <= k:
            beautiful_indices.append(a_idx)
        # Also check the next few b indices that might be in range
        else:
            temp_j = j
            while temp_j < len(indices_b) and indices_b[temp_j] <= a_idx + k:
                if abs(indices_b[temp_j] - a_idx) <= k:
                    beautiful_indices.append(a_idx)
                    break
                temp_j += 1
  
    return beautiful_indices

The most critical issue is the first pitfall - the two-pointer logic needs to be completely restructured to handle cases where multiple a indices need to check against overlapping ranges of b indices.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers