Facebook Pixel

3008. Find Beautiful Indices in the Given Array II

HardTwo PointersStringBinary SearchString MatchingHash FunctionRolling Hash
Leetcode Link

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:

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

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

  3. 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:

  1. Find all positions where pattern a occurs in string s
  2. 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 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.

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

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

Since |resa| ≤ n/len(a) and |resb| ≤ n/len(b), and assuming m represents the total number of pattern occurrences, the overall complexity is O(n + m*len(a) + m*len(b) + |resa| * |resb|).

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:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More