3008. Find Beautiful Indices in the Given Array II

HardTwo 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.

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 appears in string s, and this occurrence must be within distance k from index i. Specifically:
- j must be a valid starting position for pattern b: 0 <= j <= s.length - b.length
- The substring starting at j must match pattern b: s[j..(j + b.length - 1)] == b
- The distance between i and j must not exceed k: |j - i| <= k

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

For example, if s = "isawsquirrelnearsquirrelhere", a = "squirrel", b = "near", and k = 15, you would need to find all positions where "squirrel" appears and check if "near" appears within 15 positions of each occurrence.

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 in a string and then determine which occurrences of the first pattern have at least one occurrence of the second pattern within a specified distance.

The naive approach would be to check every possible position in string s to see if pattern a starts there, and for each match, scan the surrounding area to find pattern b. However, this would involve repeated substring comparisons, leading to inefficient time complexity.

The key insight is to break this problem into two independent sub-problems:

Find all positions where pattern a occurs in string s
Find all positions where pattern b occurs in string s

Once we have these two lists of positions, we can efficiently check which positions from the first list have at least one position from the second list within distance k.

For finding pattern occurrences, the KMP algorithm is ideal because it avoids redundant comparisons by utilizing a prefix function. When a mismatch occurs, instead of starting over from the next character, KMP uses previously computed information about the pattern to skip unnecessary comparisons. This reduces the pattern searching from O(n*m) to O(n+m) time complexity.

After obtaining the two sorted lists of occurrences (resa for pattern a and resb for pattern b), we need to determine which indices in resa are "beautiful". For each index in resa, we need to check if there's at least one index in resb within distance k.

The solution uses a two-pointer approach to optimize this checking process. Since both lists are sorted, we can maintain a pointer j for resb and try to find the closest occurrence of pattern b for each occurrence of pattern a. The optimization lies in not resetting j to 0 for each new i, but rather advancing it intelligently based on the distance between occurrences.

Learn more about Two Pointers and Binary Search patterns.

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 where pattern a occurs and 5 there exists an occurrence of pattern b within distance k. 6 7 Args: 8 s: The main string to search in 9 a: First pattern to find 10 b: Second pattern that must be within distance k of a 11 k: Maximum distance between occurrences of a and b 12 13 Returns: 14 List of indices where a occurs and b is within distance k 15 """ 16 17 def build_prefix_function(pattern: str) -> List[int]: 18 """ 19 Build the prefix function (failure function) for KMP algorithm. 20 21 The prefix function at position i indicates the length of the longest 22 proper prefix of pattern[0...i] which is also a suffix. 23 24 Args: 25 pattern: The pattern string to build prefix function for 26 27 Returns: 28 List containing prefix function values 29 """ 30 prefix_function = [0] * len(pattern) 31 j = 0 # Length of current longest prefix suffix 32 33 for i in range(1, len(pattern)): 34 # Find the longest prefix suffix for pattern[0...i] 35 while j > 0 and pattern[i] != pattern[j]: 36 j = prefix_function[j - 1] 37 38 if pattern[i] == pattern[j]: 39 j += 1 40 41 prefix_function[i] = j 42 43 return prefix_function 44 45 def kmp_search(pattern: str, text: str, prefix_function: List[int]) -> List[int]: 46 """ 47 Find all occurrences of pattern in text using KMP algorithm. 48 49 Args: 50 pattern: The pattern to search for 51 text: The text to search in 52 prefix_function: Pre-computed prefix function for the pattern 53 54 Returns: 55 List of starting indices where pattern occurs in text 56 """ 57 occurrences = [] 58 j = 0 # Current position in pattern 59 60 for i in range(len(text)): 61 # Adjust pattern position while there's a mismatch 62 while j > 0 and text[i] != pattern[j]: 63 j = prefix_function[j - 1] 64 65 # Character matches, move to next position in pattern 66 if text[i] == pattern[j]: 67 j += 1 68 69 # Complete pattern found 70 if j == len(pattern): 71 occurrences.append(i - j + 1) # Add starting index 72 j = prefix_function[j - 1] # Continue searching 73 74 return occurrences 75 76 # Build prefix functions for both patterns 77 prefix_a = build_prefix_function(a) 78 prefix_b = build_prefix_function(b) 79 80 # Find all occurrences of patterns a and b in string s 81 indices_a = kmp_search(a, s, prefix_a) 82 indices_b = kmp_search(b, s, prefix_b) 83 84 # Find beautiful indices where a occurs and b is within distance k 85 beautiful_indices = [] 86 i = 0 # Pointer for indices_a 87 j = 0 # Pointer for indices_b 88 89 while i < len(indices_a): 90 # Reset j pointer for each a index to check all b indices 91 j = 0 92 while j < len(indices_b): 93 # Check if current b index is within distance k from current a index 94 if abs(indices_b[j] - indices_a[i]) <= k: 95 beautiful_indices.append(indices_a[i]) 96 break # Found a valid b, move to next a 97 98 # Try to find a closer b index if possible 99 elif j + 1 < len(indices_b) and abs(indices_b[j + 1] - indices_a[i]) < abs(indices_b[j] - indices_a[i]): 100 j += 1 # Move to next b index as it's closer 101 else: 102 break # No closer b index available 103 104 i += 1 105 106 return beautiful_indices 107

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

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

1/** 2 * Finds all beautiful indices in string s where patternA occurs and 3 * there exists an occurrence of patternB within distance k 4 * @param s - The input string to search in 5 * @param patternA - The first pattern to find 6 * @param patternB - The second pattern that must be within distance k 7 * @param k - Maximum distance between patternA and patternB occurrences 8 * @returns Array of beautiful indices (starting positions of patternA) 9 */ 10function beautifulIndices(s: string, patternA: string, patternB: string, k: number): number[] { 11 // Find all occurrences of patternA in string s using KMP algorithm 12 const indicesA: number[] = kmpSearch(s, patternA); 13 14 // Find all occurrences of patternB in string s using KMP algorithm 15 const indicesB: number[] = kmpSearch(s, patternB); 16 17 // Sort indicesB for binary search (though KMP returns sorted indices, explicit sort for clarity) 18 indicesB.sort((a, b) => a - b); 19 20 const result: number[] = []; 21 22 // For each occurrence of patternA, check if there exists a valid patternB within distance k 23 for (const indexA of indicesA) { 24 // Find the range of indicesB that could potentially be within distance k from indexA 25 // Left boundary: first index >= (indexA - k) 26 const leftIdx = lowerBound(indicesB, indexA - k); 27 28 // Right boundary: first index > (indexA + k) 29 const rightIdx = upperBound(indicesB, indexA + k); 30 31 // Check if any indexB in the range satisfies the distance constraint 32 let foundValid = false; 33 for (let i = leftIdx; i < rightIdx; i++) { 34 if (Math.abs(indicesB[i] - indexA) <= k) { 35 result.push(indexA); 36 foundValid = true; 37 break; 38 } 39 } 40 } 41 42 return result; 43} 44 45/** 46 * KMP pattern matching algorithm to find all occurrences of pattern in text 47 * @param text - The text to search in 48 * @param pattern - The pattern to search for 49 * @returns Array of starting indices where pattern occurs in text 50 */ 51function kmpSearch(text: string, pattern: string): number[] { 52 const matchIndices: number[] = []; 53 54 // Build the prefix function (failure function) for the pattern 55 const prefixTable: number[] = computePrefixFunction(pattern); 56 57 // Number of characters matched so far 58 let matchedChars = 0; 59 60 // Traverse through the text 61 for (let i = 0; i < text.length; i++) { 62 // While there's a mismatch and we haven't reached the beginning of pattern 63 while (matchedChars > 0 && pattern[matchedChars] !== text[i]) { 64 // Use prefix table to skip characters 65 matchedChars = prefixTable[matchedChars - 1]; 66 } 67 68 // If current characters match, increment matched count 69 if (pattern[matchedChars] === text[i]) { 70 matchedChars++; 71 } 72 73 // If entire pattern is matched 74 if (matchedChars === pattern.length) { 75 // Add starting index of the match 76 matchIndices.push(i - matchedChars + 1); 77 // Continue searching for next occurrence 78 matchedChars = prefixTable[matchedChars - 1]; 79 } 80 } 81 82 return matchIndices; 83} 84 85/** 86 * Compute the prefix function (failure function) for KMP algorithm 87 * @param pattern - The pattern to compute prefix function for 88 * @returns Array representing the prefix function values 89 */ 90function computePrefixFunction(pattern: string): number[] { 91 const patternLength = pattern.length; 92 const prefixTable: number[] = new Array(patternLength).fill(0); 93 94 // Length of the longest proper prefix which is also suffix 95 let prefixLength = 0; 96 97 // Build the prefix table 98 for (let i = 1; i < patternLength; i++) { 99 // While there's a mismatch, fall back using previous values 100 while (prefixLength > 0 && pattern[prefixLength] !== pattern[i]) { 101 prefixLength = prefixTable[prefixLength - 1]; 102 } 103 104 // If characters match, extend the prefix length 105 if (pattern[prefixLength] === pattern[i]) { 106 prefixLength++; 107 } 108 109 // Store the computed prefix length for position i 110 prefixTable[i] = prefixLength; 111 } 112 113 return prefixTable; 114} 115 116/** 117 * Binary search to find the first index in array where value >= target 118 * @param arr - Sorted array to search in 119 * @param target - Target value to find 120 * @returns Index of first element >= target, or array length if none exist 121 */ 122function lowerBound(arr: number[], target: number): number { 123 let left = 0; 124 let right = arr.length; 125 126 while (left < right) { 127 const mid = Math.floor((left + right) / 2); 128 if (arr[mid] < target) { 129 left = mid + 1; 130 } else { 131 right = mid; 132 } 133 } 134 135 return left; 136} 137 138/** 139 * Binary search to find the first index in array where value > target 140 * @param arr - Sorted array to search in 141 * @param target - Target value to find 142 * @returns Index of first element > target, or array length if none exist 143 */ 144function upperBound(arr: number[], target: number): number { 145 let left = 0; 146 let right = arr.length; 147 148 while (left < right) { 149 const mid = Math.floor((left + right) / 2); 150 if (arr[mid] <= target) { 151 left = mid + 1; 152 } else { 153 right = mid; 154 } 155 } 156 157 return left; 158} 159

Solution Approach

The solution implements the KMP (Knuth-Morris-Pratt) algorithm to efficiently find pattern occurrences, followed by a two-pointer technique to identify 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 helps KMP skip unnecessary comparisons.

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 matching prefix. When characters don't match, we use the prefix function to jump back to a previous position where we might find a match.

Step 2: KMP Pattern 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 j equals the pattern length, we've found a complete match at position i - j + 1. After finding a match, we use the prefix function to continue searching for overlapping occurrences.

Step 3: Finding Beautiful Indices

After obtaining all occurrences of patterns a and b:

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

We iterate through each occurrence of pattern a and check if there's an occurrence of pattern b within distance k:

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

The inner loop tries to find the closest occurrence of pattern b to the current occurrence of pattern a. If the distance is within k, we add the index to our result. The optimization checks if the next occurrence of b would be closer to the current occurrence of a before advancing the pointer.

Time Complexity: O(n + m1 + m2) where n is the length of string s, m1 is the length of pattern a, and m2 is the length of pattern b. The KMP searches are linear, and the final checking phase is also linear since we traverse each list at most once.

Space Complexity: O(m1 + m2 + p + q) where p and q are the number of occurrences of patterns a and b respectively.

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 work through a small example to illustrate the solution approach.

Given:

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

Step 1: Build Prefix Functions

For pattern a = "ab":

Position 0 ('a'): prefix_function[0] = 0 (by definition)
Position 1 ('b'): 'b' ≠ 'a', so prefix_function[1] = 0

For pattern b = "abc":

Position 0 ('a'): prefix_function[0] = 0
Position 1 ('b'): 'b' ≠ 'a', so prefix_function[1] = 0
Position 2 ('c'): 'c' ≠ 'a', so prefix_function[2] = 0

Step 2: Find All Occurrences Using KMP

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

i=0: 'a'='a', j=1
i=1: 'b'='b', j=2 → Found match at position 0
i=2: 'a'='a', j=1
i=3: 'b'='b', j=2 → Found match at position 2
i=4: 'c'≠'a', j=0
i=5: 'a'='a', j=1
i=6: 'b'='b', j=2 → Found match at position 5

Result: resa = [0, 2, 5]

Finding b = "abc" in s = "ababcab":

i=0: 'a'='a', j=1
i=1: 'b'='b', j=2
i=2: 'a'≠'c', reset j using prefix function
i=2: 'a'='a', j=1
i=3: 'b'='b', j=2
i=4: 'c'='c', j=3 → Found match at position 2
Continue searching...

Result: resb = [2]

Step 3: Find Beautiful Indices

Now check which indices in resa = [0, 2, 5] have an occurrence from resb = [2] within distance k=2:

For resa[0] = 0:
- Check distance to resb[0] = 2: |2 - 0| = 2 ≤ 2 ✓
- Index 0 is beautiful!
For resa[1] = 2:
- Check distance to resb[0] = 2: |2 - 2| = 0 ≤ 2 ✓
- Index 2 is beautiful!
For resa[2] = 5:
- Check distance to resb[0] = 2: |2 - 5| = 3 > 2 ✗
- Index 5 is not beautiful

Final Result: [0, 2]

These are the positions where pattern "ab" starts and pattern "abc" appears within distance 2.

Time and Space Complexity

Time Complexity: O(n + m*len(a) + m*len(b) + |resa| * |resb|)

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)) where n = len(s)
KMP search for pattern b in string s: O(n + len(b))
The final while loop to find beautiful indices: In the worst case, for each element in resa, we might iterate through all elements in resb, giving O(|resa| * |resb|) where |resa| and |resb| are the number of occurrences of patterns a and b respectively

In the worst case where the patterns are very small (like single characters) and occur frequently, this could approach O(n²).

Space Complexity: O(len(a) + len(b) + |resa| + |resb|)

Breaking down the space complexity:

Prefix function array for pattern a: O(len(a))
Prefix function array for pattern b: O(len(b))
List to store occurrences of pattern a: O(|resa|)
List to store occurrences of pattern b: O(|resb|)
Result list: O(|resa|) in the worst case

The total space complexity is O(len(a) + len(b) + |resa| + |resb|).

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

Common Pitfalls

1. Inefficient Beautiful Index Checking

The Pitfall: The current implementation resets the j pointer to 0 for each occurrence of pattern a. This creates inefficiency when both patterns have many occurrences, potentially leading to O(p*q) comparisons where p and q are the number of occurrences of patterns a and b respectively.

# Current inefficient approach while i < len(indices_a):  j = 0 # Resetting j to 0 for each a index  while j < len(indices_b):  if abs(indices_b[j] - indices_a[i]) <= k:  beautiful_indices.append(indices_a[i])  break

The Solution: Use a two-pointer technique that maintains the position of j across iterations, taking advantage of the sorted nature of both occurrence lists:

beautiful_indices = [] j = 0 # Initialize j outside the loop  for i in range(len(indices_a)):  # Move j backward if needed (when current b indices are too far ahead)  while j > 0 and indices_b[j] - indices_a[i] > k:  j -= 1   # Move j forward to find the first b index in range  while j < len(indices_b) and indices_a[i] - indices_b[j] > k:  j += 1   # Check if current j is within range  if j < len(indices_b) and abs(indices_b[j] - indices_a[i]) <= k:  beautiful_indices.append(indices_a[i])  # Also check j-1 if it exists (might be in range from the left)  elif j > 0 and abs(indices_b[j-1] - indices_a[i]) <= k:  beautiful_indices.append(indices_a[i])

2. Empty Pattern Handling

The Pitfall: The KMP implementation doesn't explicitly handle empty patterns, which could cause issues:

# This could fail with empty patterns prefix_function = [0] * len(pattern) # Empty list for empty pattern for i in range(1, len(pattern)): # No iterations for empty pattern

The Solution: Add early returns for edge cases:

def kmp_search(pattern: str, text: str, prefix_function: List[int]) -> List[int]:  if not pattern: # Handle empty pattern  return []  if len(pattern) > len(text): # Pattern longer than text  return []   # Continue with normal KMP...

3. Incorrect Distance Calculation Logic

The Pitfall: The current logic for finding the closest b index has a flaw - it only checks if the next index is closer but doesn't continue searching for potentially valid indices beyond:

# Current problematic logic elif j + 1 < len(indices_b) and abs(indices_b[j + 1] - indices_a[i]) < abs(indices_b[j] - indices_a[i]):  j += 1 # Move to next b index else:  break # Stops too early

The Solution: Use a sliding window approach or check all b indices within the range [indices_a[i] - k, indices_a[i] + k]:

def find_beautiful_indices(indices_a, indices_b, k):  beautiful_indices = []   for a_idx in indices_a:  # Binary search to find b indices in range [a_idx - k, a_idx + k]  left = bisect.bisect_left(indices_b, a_idx - k)  right = bisect.bisect_right(indices_b, a_idx + k)   # If any b index exists in the range  if left < right:  beautiful_indices.append(a_idx)   return beautiful_indices

4. KMP Prefix Function Building for Patterns with Repeated Characters

The Pitfall: While the KMP implementation is correct, developers often misunderstand how the prefix function handles patterns with many repeated characters, potentially leading to incorrect manual optimizations.

The Solution: Trust the KMP algorithm and avoid manual optimizations. The prefix function correctly handles all patterns, including those with many repetitions. Test thoroughly with edge cases like:

pattern = "aaaa"
pattern = "abab"
pattern = "abcabc"

The key is understanding that the prefix function's backtracking through j = prefix_function[j - 1] automatically handles these cases efficiently.

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

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don't know