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.

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

Pseudo-code:

python
result = []
for i from 0 to len(s) - len(a):
    if s[i : i+len(a)] == a:
        found_close_b = False
        for j from 0 to len(s) - len(b):
            if s[j : j+len(b)] == b and abs(i - j) <= k:
                found_close_b = True
                break
        if found_close_b:
            result.append(i)
return 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.

Core Insight for Find Beautiful Indices in the Given Array II

The problem can be decomposed into two distinct phases:

1. Search Phase: Identify all indices where string a appears and all indices where string b appears.
2. 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.

Execution Flow

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

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]

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

3. Search b in s:

   • Naive or KMP scan finds b at indices 1 and 3.
   • indices_b = [1, 3]

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

5. Result: [0, 2].

Proof of Correctness

The correctness relies on two pillars:

1. 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").
2. 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.

Reference Implementation

C++ Solution for LeetCode 3008

cpp
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

class Solution {
public:
    // Helper function to compute the LPS array for KMP
    vector<int> computeLPS(const string& pattern) {
        int m = pattern.length();
        vector<int> lps(m, 0);
        int len = 0; // Length of the previous longest prefix suffix
        int i = 1;

        while (i < m) {
            if (pattern[i] == pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    // KMP Search function to find all starting indices of pattern in text
    vector<int> kmpSearch(const string& text, const string& pattern) {
        vector<int> indices;
        if (pattern.empty()) return indices;
        
        vector<int> lps = computeLPS(pattern);
        int n = text.length();
        int m = pattern.length();
        int i = 0; // index for text
        int j = 0; // index for pattern

        while (i < n) {
            if (pattern[j] == text[i]) {
                j++;
                i++;
            }
            if (j == m) {
                indices.push_back(i - j);
                j = lps[j - 1]; // Reset j to find overlapping matches
            } else if (i < n && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return indices;
    }

    vector<int> beautifulIndices(string s, string a, string b, int k) {
        // Step 1: Find all occurrences of a and b using KMP
        vector<int> indices_a = kmpSearch(s, a);
        vector<int> indices_b = kmpSearch(s, b);
        
        vector<int> result;
        
        // Step 2: Filter indices of a based on distance to indices of b
        // Using binary search (lower_bound) since indices_b is sorted
        for (int i : indices_a) {
            // Find the first index in b that is >= i - k
            auto it = lower_bound(indices_b.begin(), indices_b.end(), i - k);
            
            // Check if such an index exists and is within the upper bound i + k
            if (it != indices_b.end() && *it <= i + k) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

Java Solution for LeetCode 3008

java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    // Helper to compute LPS array
    private int[] computeLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
        
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    // KMP Search implementation
    private List<Integer> kmpSearch(String text, String pattern) {
        List<Integer> indices = new ArrayList<>();
        if (pattern.isEmpty()) return indices;
        
        int[] lps = computeLPS(pattern);
        int n = text.length();
        int m = pattern.length();
        int i = 0;
        int j = 0;
        
        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                j++;
                i++;
            }
            if (j == m) {
                indices.add(i - j);
                j = lps[j - 1];
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return indices;
    }

    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
        List<Integer> indicesA = kmpSearch(s, a);
        List<Integer> indicesB = kmpSearch(s, b);
        List<Integer> result = new ArrayList<>();
        
        // Filter indices
        for (int i : indicesA) {
            // Binary search for the first index in B >= i - k
            int searchVal = i - k;
            int idx = Collections.binarySearch(indicesB, searchVal);
            
            // binarySearch returns (-(insertion point) - 1) if not found
            if (idx < 0) {
                idx = -idx - 1;
            }
            
            // Check if valid index exists within range
            if (idx < indicesB.size() && indicesB.get(idx) <= i + k) {
                result.add(i);
            }
        }
        
        return result;
    }
}

Python Solution for LeetCode 3008

python
from typing import List
import bisect

class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        
        def compute_lps(pattern):
            m = len(pattern)
            lps = [0] * m
            length = 0
            i = 1
            while i < m:
                if pattern[i] == pattern[length]:
                    length += 1
                    lps[i] = length
                    i += 1
                else:
                    if length != 0:
                        length = lps[length - 1]
                    else:
                        lps[i] = 0
                        i += 1
            return lps

        def kmp_search(text, pattern):
            indices = []
            if not pattern:
                return indices
            
            lps = compute_lps(pattern)
            n = len(text)
            m = len(pattern)
            i = 0  # index for text
            j = 0  # index for pattern
            
            while i < n:
                if pattern[j] == text[i]:
                    i += 1
                    j += 1
                
                if j == m:
                    indices.append(i - j)
                    j = lps[j - 1]
                elif i < n and pattern[j] != text[i]:
                    if j != 0:
                        j = lps[j - 1]
                    else:
                        i += 1
            return indices

        # Step 1: Get all occurrences
        indices_a = kmp_search(s, a)
        indices_b = kmp_search(s, b)
        
        result = []
        
        # Step 2: Check distance constraint
        # indices_b is sorted, so we can use binary search
        for i in indices_a:
            # Find the first index in indices_b that is >= i - k
            idx = bisect.bisect_left(indices_b, i - k)
            
            # Check if this index exists and is <= i + k
            if idx < len(indices_b) and indices_b[idx] <= i + k:
                result.append(i)
                
        return result