# Find Beautiful Indices in the Given Array II
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-beautiful-indices-in-the-given-array-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-beautiful-indices-in-the-given-array-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** String
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies)
---
## Problem
You are given a **0-indexed** string `s`, a string `a`, a string `b`, and an integer `k`.

An index `i` is **beautiful** if:

* `0 <= i <= s.length - a.length`
* `s[i..(i + a.length - 1)] == a`
* There exists an index `j` such that:  
  * `0 <= j <= s.length - b.length`
  * `s[j..(j + b.length - 1)] == b`
  * `|j - i| <= k`

Return _the array that contains beautiful indices in **sorted order from smallest to largest**_.

**Example 1:**

**Input:** s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15
**Output:** [16,33]
**Explanation:** There are 2 beautiful indices: [16,33].
- The index 16 is beautiful as s[16..17] == "my" and there exists an index 4 with s[4..11] == "squirrel" and |16 - 4| <= 15.
- The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 - 18| <= 15.
Thus we return [16,33] as the result.

**Example 2:**

**Input:** s = "abcd", a = "a", b = "a", k = 4
**Output:** [0]
**Explanation:** There is 1 beautiful index: [0].
- The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 - 0| <= 4.
Thus we return [0] as the result.

**Constraints:**

* `1 <= k <= s.length <= 5 * 105`
* `1 <= a.length, b.length <= 5 * 105`
* `s`, `a`, and `b` contain only lowercase English letters.

# Approaches
## Brute Force with Naive String Matching
This approach is a direct, straightforward implementation based on the problem description. It first finds all starting indices of substrings `a` and `b` in `s` using a naive string matching method. Then, for every occurrence of `a` at index `i`, it performs a linear scan through all occurrences of `b` at index `j` to check if the distance condition `|i - j| <= k` is satisfied.
**Time:** O(N*M_a + N*M_b + P*Q), where N is `s.length()`, M_a is `a.length()`, M_b is `b.length()`, P is `|indicesA|`, and Q is `|indicesB|`. In the worst case, this can be O(N^2), which is very inefficient. · **Space:** O(P + Q), where P and Q are the number of occurrences of `a` and `b` respectively. In the worst case, this can be O(N), where N is the length of `s`.
**Pros:** Simple to understand and implement.
**Cons:** Extremely slow due to nested loops and inefficient string searching.; Will cause a 'Time Limit Exceeded' (TLE) error on platforms with large test cases.
### Explanation
The method involves three main steps. First, we create a list `indicesA` by iterating through the string `s` and checking for `a` at every possible starting position using `substring` comparisons. Second, we do the same for string `b` to populate a list `indicesB`. Finally, we use nested loops to iterate through `indicesA` and `indicesB`. For each pair of indices `(i, j)`, we check if their absolute difference is at most `k`. If the condition holds, we add `i` to our result list and move to the next index in `indicesA` to avoid duplicates.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
        int n = s.length();
        int lenA = a.length();
        int lenB = b.length();
        List<Integer> indicesA = new ArrayList<>();
        List<Integer> indicesB = new ArrayList<>();

        for (int i = 0; i <= n - lenA; i++) {
            if (s.substring(i, i + lenA).equals(a)) {
                indicesA.add(i);
            }
        }

        for (int i = 0; i <= n - lenB; i++) {
            if (s.substring(i, i + lenB).equals(b)) {
                indicesB.add(i);
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int i : indicesA) {
            for (int j : indicesB) {
                if (Math.abs(i - j) <= k) {
                    result.add(i);
                    break;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize two empty lists, `indicesA` and `indicesB`.
- Find all occurrences of string `a` in `s`:
  - Iterate from `i = 0` to `s.length - a.length`.
  - If `s.substring(i, i + a.length)` equals `a`, add `i` to `indicesA`.
- Find all occurrences of string `b` in `s`:
  - Iterate from `j = 0` to `s.length - b.length`.
  - If `s.substring(j, j + b.length)` equals `b`, add `j` to `indicesB`.
- Initialize an empty list `result`.
- For each index `i` in `indicesA`:
  - For each index `j` in `indicesB`:
    - If `|i - j| <= k`, add `i` to `result` and break the inner loop to check the next `i`.
- Return `result`.

## Optimized String Matching with KMP and Binary Search
This approach significantly improves performance by using more sophisticated algorithms. It replaces the naive O(N*M) string search with the Knuth-Morris-Pratt (KMP) algorithm, which finds all occurrences in O(N+M) time. After obtaining the sorted lists of indices for `a` and `b`, it then uses binary search for each index of `a` to efficiently find a nearby index of `b`, reducing the search complexity from quadratic to log-linear.
**Time:** O(N + M_a + M_b + P * log(Q)), where P is `|indicesA|` and Q is `|indicesB|`. This is dominated by the search part, resulting in an effective complexity of O(N log N). · **Space:** O(N + M_a + M_b) to store the indices and the LPS arrays for KMP.
**Pros:** Much more efficient than the brute-force approach.; Passes most test cases due to the O(N log N) time complexity.
**Cons:** While much faster than brute force, the `O(N log N)` complexity might still be too slow for the tightest time limits.; The binary search part can be further optimized to achieve linear time.
### Explanation
The core of this approach is optimization. First, we find all occurrences of `a` and `b` using KMP, which is a linear-time string searching algorithm. This gives us two sorted lists, `indicesA` and `indicesB`. Then, for each index `i` in `indicesA`, we need to check if there's an index `j` in `indicesB` within the range `[i - k, i + k]`. Instead of a linear scan, we can leverage the sorted nature of `indicesB` and use binary search. Specifically, for each `i`, we search for the smallest `j` in `indicesB` that is at least `i - k`. If this `j` exists and is also no more than `i + k`, we've found a match, and `i` is a beautiful index.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
        List<Integer> indicesA = search(s, a);
        List<Integer> indicesB = search(s, b);
        List<Integer> result = new ArrayList<>();

        if (indicesA.isEmpty() || indicesB.isEmpty()) {
            return result;
        }

        for (int i : indicesA) {
            int lowerBound = i - k;
            int upperBound = i + k;

            int low = 0, high = indicesB.size() - 1;
            int insertionPoint = indicesB.size();
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (indicesB.get(mid) >= lowerBound) {
                    insertionPoint = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }

            if (insertionPoint < indicesB.size()) {
                int j = indicesB.get(insertionPoint);
                if (j <= upperBound) {
                    result.add(i);
                }
            }
        }
        return result;
    }

    private List<Integer> search(String text, String pattern) {
        int n = text.length(), m = pattern.length();
        List<Integer> result = new ArrayList<>();
        if (m == 0 || m > n) return result;
        int[] lps = computeLPS(pattern);
        for (int i = 0, j = 0; i < n; ) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            }
            if (j == m) {
                result.add(i - j);
                j = lps[j - 1];
            } else if (i < n && text.charAt(i) != pattern.charAt(j)) {
                if (j != 0) j = lps[j - 1];
                else i++;
            }
        }
        return result;
    }

    private int[] computeLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        for (int i = 1, length = 0; i < m; ) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) length = lps[length - 1];
                else i++;
            }
        }
        return lps;
    }
}
```
### Algorithm
- Implement a helper function using the Knuth-Morris-Pratt (KMP) algorithm to find all occurrences of a pattern in a text. This involves pre-computing an LPS (Longest Proper Prefix which is also Suffix) array.
- Use the KMP helper to find all starting indices of `a` in `s` and store them in a sorted list `indicesA`.
- Similarly, find all starting indices of `b` and store them in `indicesB`.
- Initialize an empty list `result`.
- For each index `i` in `indicesA`:
  - Define the search range for an index `j` from `indicesB` as `[i - k, i + k]`.
  - Perform a binary search on `indicesB` to find if any element exists in this range. A good way is to find the lower bound for `i - k`.
  - If an index `j` is found in `indicesB` such that `i - k <= j <= i + k`, add `i` to `result`.
- Return `result`.

## Optimal Solution with KMP and Two Pointers
This is the most optimal approach, achieving linear time complexity. It uses the KMP algorithm for efficient string searching, just like the previous approach. However, it replaces the binary search step with a more efficient two-pointer technique. Since both `indicesA` and `indicesB` are sorted, we can iterate through them in a synchronized manner. For each index `i` from `indicesA`, we only need to check a small, sliding window of indices in `indicesB`. The two-pointer method avoids re-scanning parts of `indicesB`, leading to a linear time check.
**Time:** O(N + M_a + M_b). The KMP part is O(N + M_a + M_b) and the two-pointer scan is O(P + Q). Since P, Q <= N, the total time is linear. · **Space:** O(N + M_a + M_b) to store the indices and the LPS arrays for KMP.
**Pros:** Optimal time complexity, making it very fast and efficient.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** The implementation is more complex, requiring a solid understanding of both KMP and the two-pointer technique.
### Explanation
The overall strategy is to first find all occurrences of `a` and `b` using KMP, yielding sorted lists `indicesA` and `indicesB`. The key improvement is in how we check the distance condition. We use two pointers, one for `indicesA` (implicitly via the for-each loop) and one for `indicesB` (explicitly, `ptrB`). As we iterate through each `i` in `indicesA`, we advance `ptrB` to the first position where `indicesB[ptrB]` could potentially be in the valid range `[i - k, i + k]`. Because `i` is always increasing, `ptrB` never needs to move backward. We then just need to check if `indicesB[ptrB]` is indeed in the range. This single pass over both lists makes the checking phase O(P + Q), leading to an overall linear time solution.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
        List<Integer> indicesA = search(s, a);
        List<Integer> indicesB = search(s, b);
        List<Integer> result = new ArrayList<>();

        if (indicesA.isEmpty() || indicesB.isEmpty()) {
            return result;
        }

        int ptrB = 0;
        for (int i : indicesA) {
            while (ptrB < indicesB.size() && indicesB.get(ptrB) < i - k) {
                ptrB++;
            }

            if (ptrB < indicesB.size() && Math.abs(indicesB.get(ptrB) - i) <= k) {
                result.add(i);
            }
        }
        return result;
    }

    private List<Integer> search(String text, String pattern) {
        int n = text.length(), m = pattern.length();
        List<Integer> result = new ArrayList<>();
        if (m == 0 || m > n) return result;
        int[] lps = computeLPS(pattern);
        for (int i = 0, j = 0; i < n; ) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            }
            if (j == m) {
                result.add(i - j);
                j = lps[j - 1];
            } else if (i < n && text.charAt(i) != pattern.charAt(j)) {
                if (j != 0) j = lps[j - 1];
                else i++;
            }
        }
        return result;
    }

    private int[] computeLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        for (int i = 1, length = 0; i < m; ) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) length = lps[length - 1];
                else i++;
            }
        }
        return lps;
    }
}
```
### Algorithm
- Use the KMP algorithm to find all occurrences of `a` and `b`, storing them in sorted lists `indicesA` and `indicesB`.
- Initialize an empty list `result`.
- Initialize a pointer for `indicesB`, `ptrB = 0`.
- Iterate through each index `i` in `indicesA`:
  - Advance `ptrB` forward as long as `indicesB[ptrB]` is too small, i.e., `indicesB[ptrB] < i - k`.
  - After advancing `ptrB`, check if it's still within the bounds of `indicesB`.
  - If it is, check if the current `indicesB[ptrB]` is within the valid window, i.e., `|indicesB[ptrB] - i| <= k`.
  - If the condition is met, add `i` to `result`.
- Do not reset `ptrB` between iterations for `i`. It will continue from where it left off.
- Return `result`.

# Solutions
### Java

```java
public class Solution { public void computeLPS ( String pattern , int [] lps ) { int M = pattern . length (); int len = 0 ; lps [ 0 ] = 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 ++; } } } } public List < Integer > KMP_codestorywithMIK ( String pat , String txt ) { int N = txt . length (); int M = pat . length (); List < Integer > result = new ArrayList <>(); int [] lps = new int [ M ]; computeLPS ( pat , lps ); int i = 0 ; // Index for text int j = 0 ; // Index for pattern while ( i < N ) { if ( pat . charAt ( j ) == txt . charAt ( i )) { i ++; j ++; } if ( j == M ) { result . add ( i - j ); // Pattern found at index i-j+1 (If you have to return 1 Based // indexing, that's why added + 1) j = lps [ j - 1 ]; } else if ( i < N && pat . charAt ( j ) != txt . charAt ( i )) { if ( j != 0 ) { j = lps [ j - 1 ]; } else { i ++; } } } return result ; } private int lowerBound ( List < Integer > list , int target ) { int left = 0 , right = list . size () - 1 , result = list . size (); while ( left <= right ) { int mid = left + ( right - left ) / 2 ; if ( list . get ( mid ) >= target ) { result = mid ; right = mid - 1 ; } else { left = mid + 1 ; } } return result ; } public List < Integer > beautifulIndices ( String s , String a , String b , int k ) { int n = s . length (); List < Integer > i_indices = KMP_codestorywithMIK ( a , s ); List < Integer > j_indices = KMP_codestorywithMIK ( b , s ); List < Integer > result = new ArrayList <>(); for ( int i : i_indices ) { int left_limit = Math . max ( 0 , i - k ); // To avoid out of bound -> I used max(0, i-k) int right_limit = Math . min ( n - 1 , i + k ); // To avoid out of bound -> I used min(n-1, i+k) int lowerBoundIndex = lowerBound ( j_indices , left_limit ); if ( lowerBoundIndex < j_indices . size () && j_indices . get ( lowerBoundIndex ) <= right_limit ) { result . add ( i ); } } return result ; } }
```

### CPP

```cpp
class Solution {
public:
  vector<int> beautifulIndices(string s, string patternA, string patternB,
                               int k) {
    vector<int> beautifulIndicesA = kmpSearch(s, patternA);
    vector<int> beautifulIndicesB = kmpSearch(s, patternB);
    sort(beautifulIndicesB.begin(), beautifulIndicesB.end());
    vector<int> result;
    for (int indexA : beautifulIndicesA) {
      int left = lower_bound(beautifulIndicesB.begin(), beautifulIndicesB.end(),
                             indexA - k) -
                 beautifulIndicesB.begin();
      int right =
          lower_bound(beautifulIndicesB.begin(), beautifulIndicesB.end(),
                      indexA + k + patternB.length()) -
          beautifulIndicesB.begin();
      left = (left >= 0) ? left : -(left + 1);
      right = (right >= 0) ? right : -(right + 1);
      for (int indexB = left; indexB < right; indexB++) {
        if (abs(beautifulIndicesB[indexB] - indexA) <= k) {
          result.push_back(indexA);
          break;
        }
      }
    }
    return result;
  }

private:
  vector<int> kmpSearch(string text, string pattern) {
    vector<int> indices;
    vector<int> pi = computePrefixFunction(pattern);
    int q = 0;
    for (int i = 0; i < text.length(); i++) {
      while (q > 0 && pattern[q] != text[i]) {
        q = pi[q - 1];
      }
      if (pattern[q] == text[i]) {
        q++;
      }
      if (q == pattern.length()) {
        indices.push_back(i - q + 1);
        q = pi[q - 1];
      }
    }
    return indices;
  }
  vector<int> computePrefixFunction(string pattern) {
    int m = pattern.length();
    vector<int> pi(m, 0);
    int k = 0;
    for (int q = 1; q < m; q++) {
      while (k > 0 && pattern[k] != pattern[q]) {
        k = pi[k - 1];
      }
      if (pattern[k] == pattern[q]) {
        k++;
      }
      pi[q] = k;
    }
    return pi;
  }
};

```

### Python

```python
class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]: def build_prefix_function(pattern): 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 return prefix_function def kmp_search(pattern, text, 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] return occurrences prefix_a = build_prefix_function(a) prefix_b = build_prefix_function(b) resa = kmp_search(a, s, prefix_a) resb = kmp_search(b, s, prefix_b) res = [] print(resa, resb) 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 return res

```