Problem editorial

Find Beautiful Indices in the Given Array II

HardString Manipulation PatternsTwo PointersStringBinary Search

Editorial

Core insight

Find Beautiful Indices in the Given Array II · String Manipulation Patterns

Core Insight for Find Beautiful Indices in the Given Array II

The problem can be decomposed into two distinct phases:

Search Phase: Identify all indices where string a appears and all indices where string b appears.
Filter Phase: For each index of a, determine if a valid index of b exists within the range [i - k, i + k].

The Search Phase is the bottleneck. Naive matching rescans characters in s repeatedly. The core insight of KMP is to utilize the internal structure of the pattern (specifically, repeating prefixes) to skip unnecessary comparisons. By preprocessing the pattern into a Longest Prefix Suffix (LPS) array, we can determine exactly how far to shift the pattern when a mismatch occurs, ensuring the pointer in s never moves backward.

The Filter Phase can be optimized by noting that the indices found will be sorted naturally (since we scan s from left to right). If we have a sorted list of indices for b, we can efficiently check for the existence of a value in the range [i - k, i + k] using binary search (specifically lower_bound) or a two-pointer approach.

Visual Description: Imagine sliding pattern a over text s. When a mismatch occurs at index j of the pattern, instead of sliding the pattern by just one character and restarting the comparison from the beginning of the pattern, we consult the LPS array. The LPS value at j-1 tells us the length of the longest proper prefix of a[0...j-1] that is also a suffix of a[0...j-1]. We shift the pattern so that this prefix aligns with the matching suffix we just saw in the text. This allows the text pointer to continue moving forward continuously.

String Matching - Naive / KMP / Rabin-Karp Pattern Visualization for LeetCode 3008: Find Beautiful Indices in the Given Array II

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 3008: Find Beautiful Indices in the Given Array II Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses the Knuth-Morris-Pratt (KMP) algorithm to efficiently find all occurrence indices of strings a and b in s, then filters the indices of a by checking if any index of b falls within the allowed distance k using binary search or two pointers.

This problem asks us to identify specific starting positions in a string s. A starting position i is considered "beautiful" if the substring starting at i matches string a, and there is another position j nearby (within distance k) where the substring matches string b.

The challenge in LeetCode 3008 lies in the constraints. The strings can be up to 500,000 characters long. A naive comparison would result in a Time Limit Exceeded (TLE), necessitating an efficient string matching algorithm.

Brute Force Approach for Find Beautiful Indices in the Given Array II

The brute force approach attempts to simulate the problem statement literally without optimization.

Iterate through every index i in s.
For each i, check if the substring s[i...i+len(a)-1] equals a.
If it matches, iterate through every index j in s.
Check if s[j...j+len(b)-1] equals b AND if |i - j| <= k.
If both conditions are met, add i to the result list.

Pseudo-code:

python

1result = []
2for i from 0 to len(s) - len(a):
3    if s[i : i+len(a)] == a:
4        found_close_b = False
5        for j from 0 to len(s) - len(b):
6            if s[j : j+len(b)] == b and abs(i - j) <= k:
7                found_close_b = True
8                break
9        if found_close_b:
10            result.append(i)
11return result

Time Complexity Analysis: The string slicing and comparison take $O(|a|)$ and $O(|b|)$ respectively. The nested loops structure implies we might perform comparisons $O(|s|^2)$ times. In the worst case, the complexity approaches $O(|s|^2 \cdot \max(|a|, |b|))$ . With $|s| = 5 \cdot 10^5$ , $|s|^2$ is $2.5 \cdot 10^{11}$ , which is far beyond the limit of roughly $10^8$ operations allowed in one second. This approach fails due to Time Limit Exceeded.

Algorithm Strategy: String Manipulation Patterns

We will implement the solution using the KMP algorithm followed by a range check.

LPS Array Construction:
- Create a helper function to generate the LPS array for a given pattern string.
- LPS[i] stores the length of the longest proper prefix of the substring pattern[0...i] that is also a suffix of that substring.
KMP Search:
- Create a search function that takes text s and pattern p.
- Use the LPS array to traverse s.
- Maintain a state index q for the pattern. If s[i] matches p[q], increment q.
- If q reaches the length of the pattern, record the starting index i - len(p) + 1 and reset q using the LPS array to allow for overlapping matches.
Index Collection:
- Run KMP for s and a to get indices_a.
- Run KMP for s and b to get indices_b.
Distance Verification:
- Iterate through each index i in indices_a.
- We need to find if there exists a j in indices_b such that i - k <= j <= i + k.
- Since indices_b is sorted, use binary search (e.g., std::lower_bound in C++ or bisect_left in Python) to find the first index in indices_b that is greater than or equal to i - k.
- Check if this found index is effectively less than or equal to i + k. If so, i is beautiful.

Execution Flow

Let's trace the logic with s = "ababa", a = "aba", b = "b", k = 1.

Build LPS for a ("aba"):
- LPS[0] = 0
- "ab": prefix "a", suffix "b" -> no match -> LPS[1] = 0
- "aba": prefix "a", suffix "a" -> match length 1 -> LPS[2] = 1
- LPS array: [0, 0, 1]
Search a in s:
- Match at index 0 (s[0..2] == "aba"). indices_a adds 0.
- Continue. Overlapping match at index 2 (s[2..4] == "aba"). indices_a adds 2.
- indices_a = [0, 2]
Search b in s:
- Naive or KMP scan finds b at indices 1 and 3.
- indices_b = [1, 3]
Filter Indices:
- Check i = 0 from indices_a:
  - Target range: [-1, 1].
  - Binary search in indices_b for first value >= -1. Found 1.
  - Is 1 <= 1? Yes. Add 0 to result.
- Check i = 2 from indices_a:
  - Target range: [1, 3].
  - Binary search in indices_b for first value >= 1. Found 1.
  - Is 1 <= 3? Yes. Add 2 to result.
Result: [0, 2].

Proof of Correctness

The correctness relies on two pillars:

Completeness of KMP: The KMP algorithm is mathematically proven to find all occurrences of a pattern in a text. By resetting the pattern index q to LPS[q-1] after a full match, we ensure overlapping occurrences are detected (e.g., finding "ana" twice in "banana").
Validity of Range Check: The problem requires |i - j| <= k, which is equivalent to i - k <= j <= i + k. By finding the smallest j in indices_b such that j >= i - k (using binary search), we identify the only candidate that could possibly satisfy the lower bound condition while being minimal. If this candidate also satisfies j <= i + k, the condition is met. If the smallest valid candidate exceeds i + k, then no other candidate can satisfy the upper bound, as the list is sorted.

Pattern Reuse Notes

The String Matching / KMP pattern is highly reusable. Understanding how to build and use the LPS array is crucial for several hard interview questions.

LeetCode 28: Find the Index of the First Occurrence in a String: The most basic application of KMP; find the first match instead of all matches.
LeetCode 214: Shortest Palindrome: Uses the KMP LPS array logic on the string concatenated with its reverse to find the longest palindrome prefix.
LeetCode 686: Repeated String Match: Can be solved by checking if pattern B exists in repeated A using KMP.
LeetCode 796: Rotate String: Checks if one string is a rotation of another, solvable by searching for s inside goal + goal using KMP.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 3008

cpp

1#include <vector>
2#include <string>
3#include <algorithm>
4#include <cmath>
5
6using namespace std;
7
8class Solution {
9public:
10    // Helper function to compute the LPS array for KMP
11    vector<int> computeLPS(const string& pattern) {
12        int m = pattern.length();
13        vector<int> lps(m, 0);
14        int len = 0; // Length of the previous longest prefix suffix
15        int i = 1;
16
17        while (i < m) {
18            if (pattern[i] == pattern[len]) {
19                len++;
20                lps[i] = len;
21                i++;
22            } else {
23                if (len != 0) {
24                    len = lps[len - 1];
25                } else {
26                    lps[i] = 0;
27                    i++;
28                }
29            }
30        }
31        return lps;
32    }
33
34    // KMP Search function to find all starting indices of pattern in text
35    vector<int> kmpSearch(const string& text, const string& pattern) {
36        vector<int> indices;
37        if (pattern.empty()) return indices;
38        
39        vector<int> lps = computeLPS(pattern);
40        int n = text.length();
41        int m = pattern.length();
42        int i = 0; // index for text
43        int j = 0; // index for pattern
44
45        while (i < n) {
46            if (pattern[j] == text[i]) {
47                j++;
48                i++;
49            }
50            if (j == m) {
51                indices.push_back(i - j);
52                j = lps[j - 1]; // Reset j to find overlapping matches
53            } else if (i < n && pattern[j] != text[i]) {
54                if (j != 0) {
55                    j = lps[j - 1];
56                } else {
57                    i++;
58                }
59            }
60        }
61        return indices;
62    }
63
64    vector<int> beautifulIndices(string s, string a, string b, int k) {
65        // Step 1: Find all occurrences of a and b using KMP
66        vector<int> indices_a = kmpSearch(s, a);
67        vector<int> indices_b = kmpSearch(s, b);
68        
69        vector<int> result;
70        
71        // Step 2: Filter indices of a based on distance to indices of b
72        // Using binary search (lower_bound) since indices_b is sorted
73        for (int i : indices_a) {
74            // Find the first index in b that is >= i - k
75            auto it = lower_bound(indices_b.begin(), indices_b.end(), i - k);
76            
77            // Check if such an index exists and is within the upper bound i + k
78            if (it != indices_b.end() && *it <= i + k) {
79                result.push_back(i);
80            }
81        }
82        
83        return result;
84    }
85};

Java Solution for LeetCode 3008

java

1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4
5class Solution {
6    // Helper to compute LPS array
7    private int[] computeLPS(String pattern) {
8        int m = pattern.length();
9        int[] lps = new int[m];
10        int len = 0;
11        int i = 1;
12        
13        while (i < m) {
14            if (pattern.charAt(i) == pattern.charAt(len)) {
15                len++;
16                lps[i] = len;
17                i++;
18            } else {
19                if (len != 0) {
20                    len = lps[len - 1];
21                } else {
22                    lps[i] = 0;
23                    i++;
24                }
25            }
26        }
27        return lps;
28    }
29
30    // KMP Search implementation
31    private List<Integer> kmpSearch(String text, String pattern) {
32        List<Integer> indices = new ArrayList<>();
33        if (pattern.isEmpty()) return indices;
34        
35        int[] lps = computeLPS(pattern);
36        int n = text.length();
37        int m = pattern.length();
38        int i = 0;
39        int j = 0;
40        
41        while (i < n) {
42            if (pattern.charAt(j) == text.charAt(i)) {
43                j++;
44                i++;
45            }
46            if (j == m) {
47                indices.add(i - j);
48                j = lps[j - 1];
49            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
50                if (j != 0) {
51                    j = lps[j - 1];
52                } else {
53                    i++;
54                }
55            }
56        }
57        return indices;
58    }
59
60    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
61        List<Integer> indicesA = kmpSearch(s, a);
62        List<Integer> indicesB = kmpSearch(s, b);
63        List<Integer> result = new ArrayList<>();
64        
65        // Filter indices
66        for (int i : indicesA) {
67            // Binary search for the first index in B >= i - k
68            int searchVal = i - k;
69            int idx = Collections.binarySearch(indicesB, searchVal);
70            
71            // binarySearch returns (-(insertion point) - 1) if not found
72            if (idx < 0) {
73                idx = -idx - 1;
74            }
75            
76            // Check if valid index exists within range
77            if (idx < indicesB.size() && indicesB.get(idx) <= i + k) {
78                result.add(i);
79            }
80        }
81        
82        return result;
83    }
84}

Python Solution for LeetCode 3008

python

1from typing import List
2import bisect
3
4class Solution:
5    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
6        
7        def compute_lps(pattern):
8            m = len(pattern)
9            lps = [0] * m
10            length = 0
11            i = 1
12            while i < m:
13                if pattern[i] == pattern[length]:
14                    length += 1
15                    lps[i] = length
16                    i += 1
17                else:
18                    if length != 0:
19                        length = lps[length - 1]
20                    else:
21                        lps[i] = 0
22                        i += 1
23            return lps
24
25        def kmp_search(text, pattern):
26            indices = []
27            if not pattern:
28                return indices
29            
30            lps = compute_lps(pattern)
31            n = len(text)
32            m = len(pattern)
33            i = 0  # index for text
34            j = 0  # index for pattern
35            
36            while i < n:
37                if pattern[j] == text[i]:
38                    i += 1
39                    j += 1
40                
41                if j == m:
42                    indices.append(i - j)
43                    j = lps[j - 1]
44                elif i < n and pattern[j] != text[i]:
45                    if j != 0:
46                        j = lps[j - 1]
47                    else:
48                        i += 1
49            return indices
50
51        # Step 1: Get all occurrences
52        indices_a = kmp_search(s, a)
53        indices_b = kmp_search(s, b)
54        
55        result = []
56        
57        # Step 2: Check distance constraint
58        # indices_b is sorted, so we can use binary search
59        for i in indices_a:
60            # Find the first index in indices_b that is >= i - k
61            idx = bisect.bisect_left(indices_b, i - k)
62            
63            # Check if this index exists and is <= i + k
64            if idx < len(indices_b) and indices_b[idx] <= i + k:
65                result.append(i)
66                
67        return result

AI Coach Insight

For Find Beautiful Indices in the Given Array II, focus on explaining why the structure works, not just naming String Manipulation Patterns.

Complexity Analysis

Let $N$ be the length of s, $A$ be the length of a, and $B$ be the length of b.

Time Complexity: $O(N + A + B)$
- Building LPS for a: $O(A)$ .
- Building LPS for b: $O(B)$ .
- Scanning s for a: $O(N)$ .
- Scanning s for b: $O(N)$ .
- Filtering: Let $K_A$ and $K_B$ be the number of occurrences of a and b. The loop runs $K_A$ times. Inside, binary search takes $O(\log K_B)$ . Total filtering is $O(K_A \log K_B)$ . Since $K_A, K_B \le N$ , this is bounded by $O(N \log N)$ .
- Using a two-pointer approach for filtering would reduce the check to $O(K_A + K_B)$ , making the total strictly linear $O(N)$ . Both are acceptable for these constraints.
Space Complexity: $O(N)$
- LPS arrays take $O(A)$ and $O(B)$ .
- Storing indices_a and indices_b takes up to $O(N)$ space in the worst case (e.g., s="aaaa", a="a").

Related Patterns

Pattern: String Manipulation Patterns
Subpattern: String Matching - Naive / KMP / Rabin-Karp

This problem is a classic application of efficient string matching. We need to find all occurrences of a pattern within a text multiple times. The KMP (Knuth-Morris-Pratt) algorithm is the standard tool for this, offering linear time complexity $O(N + M)$ where $N$ is the text length and $M$ is the pattern length.

Common Mistakes & FAQ

Why does my naive solution get Time Limit Exceeded (TLE)?
- Mistake: Using standard library functions like .find() or manual loops inside a loop without KMP logic.
- Reason: Standard string search can degrade to $O(N \cdot M)$ in worst-case scenarios (e.g., searching "aaaaa" inside "aaaaaaaa"). Combined with the outer logic, this becomes too slow for inputs of size $5 \cdot 10^5$ .
- Consequence: The solution fails on large test cases.
Why is my distance check failing?
- Mistake: Iterating through all of indices_b for every i in indices_a.
- Reason: This creates a nested loop structure $O(|indices\_a| \cdot |indices\_b|)$ , which is effectively $O(N^2)$ in the worst case where matches are frequent.
- Consequence: TLE even if KMP is implemented correctly. Binary search or two pointers is required here.
Why am I missing overlapping matches?
- Mistake: In the KMP implementation, resetting the pattern index j to 0 after a match.
- Reason: If the pattern is "ana" and the text is "banana", resetting to 0 finds the first "ana" but misses the second one starting at the 'n'.
- Consequence: Incorrect output. You must reset j to lps[j-1] to preserve the prefix match.

Practise Find Beautiful Indices in the Given Array II and the problems around it

Find Beautiful Indices in the Given Array II is a String Manipulation Patterns problem, in the Naive / KMP / Rabin-Karp subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Find Beautiful Indices in the Given Array II · String Manipulation Patterns

Core Insight for Find Beautiful Indices in the Given Array II

The problem can be decomposed into two distinct phases:

Search Phase: Identify all indices where string a appears and all indices where string b appears.
Filter Phase: For each index of a, determine if a valid index of b exists within the range [i - k, i + k].

String Matching - Naive / KMP / Rabin-Karp Pattern Visualization for LeetCode 3008: Find Beautiful Indices in the Given Array II

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 3008: Find Beautiful Indices in the Given Array II Solution & Explanation

Problem Overview

Brute Force Approach for Find Beautiful Indices in the Given Array II

The brute force approach attempts to simulate the problem statement literally without optimization.

Iterate through every index i in s.
For each i, check if the substring s[i...i+len(a)-1] equals a.
If it matches, iterate through every index j in s.
Check if s[j...j+len(b)-1] equals b AND if |i - j| <= k.
If both conditions are met, add i to the result list.

Pseudo-code:

python

1result = []
2for i from 0 to len(s) - len(a):
3    if s[i : i+len(a)] == a:
4        found_close_b = False
5        for j from 0 to len(s) - len(b):
6            if s[j : j+len(b)] == b and abs(i - j) <= k:
7                found_close_b = True
8                break
9        if found_close_b:
10            result.append(i)
11return result

Algorithm Strategy: String Manipulation Patterns

We will implement the solution using the KMP algorithm followed by a range check.

LPS Array Construction:
- Create a helper function to generate the LPS array for a given pattern string.
- LPS[i] stores the length of the longest proper prefix of the substring pattern[0...i] that is also a suffix of that substring.
KMP Search:
- Create a search function that takes text s and pattern p.
- Use the LPS array to traverse s.
- Maintain a state index q for the pattern. If s[i] matches p[q], increment q.
- If q reaches the length of the pattern, record the starting index i - len(p) + 1 and reset q using the LPS array to allow for overlapping matches.
Index Collection:
- Run KMP for s and a to get indices_a.
- Run KMP for s and b to get indices_b.
Distance Verification:
- Iterate through each index i in indices_a.
- We need to find if there exists a j in indices_b such that i - k <= j <= i + k.
- Since indices_b is sorted, use binary search (e.g., std::lower_bound in C++ or bisect_left in Python) to find the first index in indices_b that is greater than or equal to i - k.
- Check if this found index is effectively less than or equal to i + k. If so, i is beautiful.

Execution Flow

Let's trace the logic with s = "ababa", a = "aba", b = "b", k = 1.

Build LPS for a ("aba"):
- LPS[0] = 0
- "ab": prefix "a", suffix "b" -> no match -> LPS[1] = 0
- "aba": prefix "a", suffix "a" -> match length 1 -> LPS[2] = 1
- LPS array: [0, 0, 1]
Search a in s:
- Match at index 0 (s[0..2] == "aba"). indices_a adds 0.
- Continue. Overlapping match at index 2 (s[2..4] == "aba"). indices_a adds 2.
- indices_a = [0, 2]
Search b in s:
- Naive or KMP scan finds b at indices 1 and 3.
- indices_b = [1, 3]
Filter Indices:
- Check i = 0 from indices_a:
  - Target range: [-1, 1].
  - Binary search in indices_b for first value >= -1. Found 1.
  - Is 1 <= 1? Yes. Add 0 to result.
- Check i = 2 from indices_a:
  - Target range: [1, 3].
  - Binary search in indices_b for first value >= 1. Found 1.
  - Is 1 <= 3? Yes. Add 2 to result.
Result: [0, 2].

Proof of Correctness

The correctness relies on two pillars:

Completeness of KMP: The KMP algorithm is mathematically proven to find all occurrences of a pattern in a text. By resetting the pattern index q to LPS[q-1] after a full match, we ensure overlapping occurrences are detected (e.g., finding "ana" twice in "banana").
Validity of Range Check: The problem requires |i - j| <= k, which is equivalent to i - k <= j <= i + k. By finding the smallest j in indices_b such that j >= i - k (using binary search), we identify the only candidate that could possibly satisfy the lower bound condition while being minimal. If this candidate also satisfies j <= i + k, the condition is met. If the smallest valid candidate exceeds i + k, then no other candidate can satisfy the upper bound, as the list is sorted.

Pattern Reuse Notes

The String Matching / KMP pattern is highly reusable. Understanding how to build and use the LPS array is crucial for several hard interview questions.

LeetCode 28: Find the Index of the First Occurrence in a String: The most basic application of KMP; find the first match instead of all matches.
LeetCode 214: Shortest Palindrome: Uses the KMP LPS array logic on the string concatenated with its reverse to find the longest palindrome prefix.
LeetCode 686: Repeated String Match: Can be solved by checking if pattern B exists in repeated A using KMP.
LeetCode 796: Rotate String: Checks if one string is a rotation of another, solvable by searching for s inside goal + goal using KMP.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 3008

cpp

1#include <vector>
2#include <string>
3#include <algorithm>
4#include <cmath>
5
6using namespace std;
7
8class Solution {
9public:
10    // Helper function to compute the LPS array for KMP
11    vector<int> computeLPS(const string& pattern) {
12        int m = pattern.length();
13        vector<int> lps(m, 0);
14        int len = 0; // Length of the previous longest prefix suffix
15        int i = 1;
16
17        while (i < m) {
18            if (pattern[i] == pattern[len]) {
19                len++;
20                lps[i] = len;
21                i++;
22            } else {
23                if (len != 0) {
24                    len = lps[len - 1];
25                } else {
26                    lps[i] = 0;
27                    i++;
28                }
29            }
30        }
31        return lps;
32    }
33
34    // KMP Search function to find all starting indices of pattern in text
35    vector<int> kmpSearch(const string& text, const string& pattern) {
36        vector<int> indices;
37        if (pattern.empty()) return indices;
38        
39        vector<int> lps = computeLPS(pattern);
40        int n = text.length();
41        int m = pattern.length();
42        int i = 0; // index for text
43        int j = 0; // index for pattern
44
45        while (i < n) {
46            if (pattern[j] == text[i]) {
47                j++;
48                i++;
49            }
50            if (j == m) {
51                indices.push_back(i - j);
52                j = lps[j - 1]; // Reset j to find overlapping matches
53            } else if (i < n && pattern[j] != text[i]) {
54                if (j != 0) {
55                    j = lps[j - 1];
56                } else {
57                    i++;
58                }
59            }
60        }
61        return indices;
62    }
63
64    vector<int> beautifulIndices(string s, string a, string b, int k) {
65        // Step 1: Find all occurrences of a and b using KMP
66        vector<int> indices_a = kmpSearch(s, a);
67        vector<int> indices_b = kmpSearch(s, b);
68        
69        vector<int> result;
70        
71        // Step 2: Filter indices of a based on distance to indices of b
72        // Using binary search (lower_bound) since indices_b is sorted
73        for (int i : indices_a) {
74            // Find the first index in b that is >= i - k
75            auto it = lower_bound(indices_b.begin(), indices_b.end(), i - k);
76            
77            // Check if such an index exists and is within the upper bound i + k
78            if (it != indices_b.end() && *it <= i + k) {
79                result.push_back(i);
80            }
81        }
82        
83        return result;
84    }
85};

Java Solution for LeetCode 3008

java

1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4
5class Solution {
6    // Helper to compute LPS array
7    private int[] computeLPS(String pattern) {
8        int m = pattern.length();
9        int[] lps = new int[m];
10        int len = 0;
11        int i = 1;
12        
13        while (i < m) {
14            if (pattern.charAt(i) == pattern.charAt(len)) {
15                len++;
16                lps[i] = len;
17                i++;
18            } else {
19                if (len != 0) {
20                    len = lps[len - 1];
21                } else {
22                    lps[i] = 0;
23                    i++;
24                }
25            }
26        }
27        return lps;
28    }
29
30    // KMP Search implementation
31    private List<Integer> kmpSearch(String text, String pattern) {
32        List<Integer> indices = new ArrayList<>();
33        if (pattern.isEmpty()) return indices;
34        
35        int[] lps = computeLPS(pattern);
36        int n = text.length();
37        int m = pattern.length();
38        int i = 0;
39        int j = 0;
40        
41        while (i < n) {
42            if (pattern.charAt(j) == text.charAt(i)) {
43                j++;
44                i++;
45            }
46            if (j == m) {
47                indices.add(i - j);
48                j = lps[j - 1];
49            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
50                if (j != 0) {
51                    j = lps[j - 1];
52                } else {
53                    i++;
54                }
55            }
56        }
57        return indices;
58    }
59
60    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
61        List<Integer> indicesA = kmpSearch(s, a);
62        List<Integer> indicesB = kmpSearch(s, b);
63        List<Integer> result = new ArrayList<>();
64        
65        // Filter indices
66        for (int i : indicesA) {
67            // Binary search for the first index in B >= i - k
68            int searchVal = i - k;
69            int idx = Collections.binarySearch(indicesB, searchVal);
70            
71            // binarySearch returns (-(insertion point) - 1) if not found
72            if (idx < 0) {
73                idx = -idx - 1;
74            }
75            
76            // Check if valid index exists within range
77            if (idx < indicesB.size() && indicesB.get(idx) <= i + k) {
78                result.add(i);
79            }
80        }
81        
82        return result;
83    }
84}

Python Solution for LeetCode 3008

python

1from typing import List
2import bisect
3
4class Solution:
5    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
6        
7        def compute_lps(pattern):
8            m = len(pattern)
9            lps = [0] * m
10            length = 0
11            i = 1
12            while i < m:
13                if pattern[i] == pattern[length]:
14                    length += 1
15                    lps[i] = length
16                    i += 1
17                else:
18                    if length != 0:
19                        length = lps[length - 1]
20                    else:
21                        lps[i] = 0
22                        i += 1
23            return lps
24
25        def kmp_search(text, pattern):
26            indices = []
27            if not pattern:
28                return indices
29            
30            lps = compute_lps(pattern)
31            n = len(text)
32            m = len(pattern)
33            i = 0  # index for text
34            j = 0  # index for pattern
35            
36            while i < n:
37                if pattern[j] == text[i]:
38                    i += 1
39                    j += 1
40                
41                if j == m:
42                    indices.append(i - j)
43                    j = lps[j - 1]
44                elif i < n and pattern[j] != text[i]:
45                    if j != 0:
46                        j = lps[j - 1]
47                    else:
48                        i += 1
49            return indices
50
51        # Step 1: Get all occurrences
52        indices_a = kmp_search(s, a)
53        indices_b = kmp_search(s, b)
54        
55        result = []
56        
57        # Step 2: Check distance constraint
58        # indices_b is sorted, so we can use binary search
59        for i in indices_a:
60            # Find the first index in indices_b that is >= i - k
61            idx = bisect.bisect_left(indices_b, i - k)
62            
63            # Check if this index exists and is <= i + k
64            if idx < len(indices_b) and indices_b[idx] <= i + k:
65                result.append(i)
66                
67        return result

Find Beautiful Indices in the Given Array II

Core insight

Core Insight for Find Beautiful Indices in the Given Array II

Full breakdown

LeetCode 3008: Find Beautiful Indices in the Given Array II Solution & Explanation

Problem Overview

Brute Force Approach for Find Beautiful Indices in the Given Array II

Algorithm Strategy: String Manipulation Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 3008

Java Solution for LeetCode 3008

Python Solution for LeetCode 3008

Practise Find Beautiful Indices in the Given Array II and the problems around it

Related problems

Find Beautiful Indices in the Given Array II

Core insight

Core Insight for Find Beautiful Indices in the Given Array II

Full breakdown

LeetCode 3008: Find Beautiful Indices in the Given Array II Solution & Explanation

Problem Overview

Brute Force Approach for Find Beautiful Indices in the Given Array II

Algorithm Strategy: String Manipulation Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 3008

Java Solution for LeetCode 3008

Python Solution for LeetCode 3008

Practise Find Beautiful Indices in the Given Array II and the problems around it

Related problems