# Find Beautiful Indices in the Given Array I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-beautiful-indices-in-the-given-array-i)
Canonical: https://scaleengineer.com/dsa/problems/find-beautiful-indices-in-the-given-array-i
**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:** [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies), [Samsara](https://scaleengineer.com/companies/samsara)
---
## 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 <= 105`
* `1 <= a.length, b.length <= 10`
* `s`, `a`, and `b` contain only lowercase English letters.

# Approaches
## Brute-Force Nested Loop
This approach is a straightforward, brute-force solution. It first identifies all occurrences of the substrings `a` and `b` within the main string `s` and stores their starting indices in two separate lists. Afterwards, it employs a pair of nested loops to compare every index from the first list against every index from the second. If any pair of indices `(i, j)` satisfies the condition `|i - j| <= k`, the index `i` is marked as beautiful and added to the result.
**Time:** O(N*M + P*Q), where N is `s.length()`, M is `max(a.length(), b.length())`, P is the count of `a`'s occurrences, and Q is the count of `b`'s occurrences. In the worst case, P and Q can be O(N), making the complexity O(N^2). · **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:** Easy to understand and implement.; Works correctly for small inputs.
**Cons:** The nested loop for checking the distance condition leads to a quadratic time complexity in the worst case, which is highly inefficient for large inputs.; It is likely to result in a 'Time Limit Exceeded' error on platforms with strict time constraints.
### Explanation
The implementation involves two main steps. First, we scan the string `s` twice to find all starting positions for `a` and `b`. A simple way to do this is by iterating from `0` to `s.length() - pattern.length()` and using `s.startsWith(pattern, i)`. The found indices are stored in `indicesA` and `indicesB`.

Second, we iterate through each index `i` in `indicesA`. For each `i`, we iterate through all indices `j` in `indicesB`. We calculate the absolute difference `|i - j|` and check if it's less than or equal to `k`. If the condition holds, we add `i` to our result list and use `break` to stop searching for other `j`'s for the current `i`, as one is sufficient.

```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<>();
        for (int i = 0; i <= n - lenA; i++) {
            if (s.startsWith(a, i)) {
                indicesA.add(i);
            }
        }

        List<Integer> indicesB = new ArrayList<>();
        for (int i = 0; i <= n - lenB; i++) {
            if (s.startsWith(b, i)) {
                indicesB.add(i);
            }
        }

        List<Integer> result = new ArrayList<>();
        if (indicesA.isEmpty() || indicesB.isEmpty()) {
            return result;
        }

        for (int i : indicesA) {
            for (int j : indicesB) {
                if (Math.abs(i - j) <= k) {
                    result.add(i);
                    break; // Found a valid j, move to the next i
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Create two lists, `indicesA` and `indicesB`, to store the starting indices of all occurrences of strings `a` and `b` in `s`.
- Populate `indicesA` by iterating through `s` and checking for `a` at each position.
- Populate `indicesB` similarly by checking for `b`.
- Initialize an empty list `result` to store the beautiful indices.
- Iterate through each index `i` in `indicesA` with an outer loop.
- Inside, use a nested loop to iterate through each index `j` in `indicesB`.
- If `Math.abs(i - j) <= k`, it means `i` is a beautiful index. Add `i` to `result` and break the inner loop to proceed to the next `i`.
- Return the `result` list.

## Pre-computation and Binary Search
This approach improves upon the brute-force method by optimizing the search for a valid index `j`. After finding all occurrences of `a` and `b` and storing their indices in sorted lists, it iterates through each index `i` from `a`'s occurrences. For each `i`, instead of a linear scan, it performs a binary search on the list of `b`'s indices. This allows for a much faster check (logarithmic time) to see if there's any index `j` within the desired range `[i - k, i + k]`.
**Time:** O(N*M + P*log(Q)). Finding indices takes O(N*M). The main loop runs P times, with each iteration taking O(log Q) for binary search. In the worst case, this is O(N*log(N)). · **Space:** O(P + Q), which can be O(N) in the worst case, for storing the indices.
**Pros:** Significantly more efficient than the brute-force approach.; Passes for larger inputs where the brute-force approach would time out.
**Cons:** While much better than brute-force, it's not the most optimal solution as it repeatedly performs a binary search for each occurrence of `a`.
### Explanation
The first step remains the same: populate `indicesA` and `indicesB` with the starting indices of `a` and `b`. Since we find them by iterating from left to right, these lists will be naturally sorted.

Next, for each index `i` in `indicesA`, we need to find if there's an index `j` in `indicesB` in the range `[i - k, i + k]`. We can do this efficiently with binary search. We search for the lower bound of `i - k` in `indicesB`. This gives us the first potential `j` that is greater than or equal to `i - k`. If this potential `j` exists and is also less than or equal to `i + k`, we have found a valid partner for `i`, so `i` is beautiful.

```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();
        List<Integer> indicesA = new ArrayList<>();
        for (int i = 0; i <= n - a.length(); i++) {
            if (s.startsWith(a, i)) {
                indicesA.add(i);
            }
        }

        List<Integer> indicesB = new ArrayList<>();
        for (int i = 0; i <= n - b.length(); i++) {
            if (s.startsWith(b, i)) {
                indicesB.add(i);
            }
        }

        List<Integer> result = new ArrayList<>();
        if (indicesA.isEmpty() || indicesB.isEmpty()) {
            return result;
        }

        for (int i : indicesA) {
            int searchStart = i - k;
            
            // Binary search for the first j >= searchStart
            int low = 0, high = indicesB.size() - 1;
            int insertionPoint = indicesB.size();
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (indicesB.get(mid) >= searchStart) {
                    insertionPoint = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }

            // Check if the found j is within the valid range [i-k, i+k]
            if (insertionPoint < indicesB.size()) {
                int j = indicesB.get(insertionPoint);
                if (Math.abs(i - j) <= k) {
                    result.add(i);
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- First, find all starting indices of `a` and `b` in `s` and store them in two sorted lists, `indicesA` and `indicesB`.
- Initialize an empty list `result`.
- Iterate through each index `i` in `indicesA`.
- For each `i`, the condition `|i - j| <= k` is equivalent to finding a `j` in `indicesB` such that `i - k <= j <= i + k`.
- Use binary search on the sorted list `indicesB` to check for the existence of such a `j`.
- To do this, search for the first element in `indicesB` that is greater than or equal to `i - k`. Let's call this element `j_candidate`.
- If `j_candidate` exists and `j_candidate <= i + k`, then `i` is a beautiful index. Add `i` to `result`.
- Return `result`.

## Two Pointers with KMP
This is the most optimal approach, achieving linear time complexity. It has two main parts. First, it uses the Knuth-Morris-Pratt (KMP) algorithm to find all occurrences of `a` and `b` in O(N) time, which is asymptotically faster than simple string matching. Second, with the two sorted lists of indices, it uses a two-pointer technique. As we iterate through `a`'s indices with one pointer, we intelligently advance the second pointer for `b`'s indices. This avoids re-scanning and allows us to check the distance condition for all indices in a single, linear pass.
**Time:** O(N + M). The KMP searches take O(N + |a|) and O(N + |b|). The two-pointer scan takes O(P + Q). Since P, Q <= N, the total complexity is dominated by the string searching, resulting in O(N + M). · **Space:** O(N + M) where N is `s.length()` and M is `max(a.length(), b.length())`. This is for storing the indices and the KMP helper arrays.
**Pros:** Achieves optimal linear time complexity.; Most efficient solution, guaranteed to pass even for very large inputs within the given constraints.
**Cons:** The implementation is more complex, requiring knowledge of advanced algorithms like KMP.
### Explanation
This approach optimizes both phases of the problem. 

1.  **Finding Occurrences with KMP:** Instead of a simple loop, we use the KMP algorithm. KMP preprocesses the pattern to create a Longest Proper Prefix Suffix (LPS) array. This array helps to avoid redundant comparisons, allowing the search for all occurrences to complete in O(N + M) time, where N is the text length and M is the pattern length.

2.  **Two-Pointer Check:** With the sorted `indicesA` and `indicesB` lists, we use two pointers, `idxA` and `idxB`, both starting at 0. We iterate through `indicesA` with `idxA`. For each `i = indicesA[idxA]`, we advance `idxB` to find the first `j = indicesB[idxB]` that could potentially be in the range `[i-k, i+k]`. We do this by skipping all `j`'s that are smaller than `i-k`. Then, we check if the current `j` is within the range. If it is, we've found a beautiful index. We then move to the next `i`. Because `idxB` never moves backward, the total work for this phase is proportional to the sum of the lengths of the two index lists, O(P + Q).

```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 = kmpSearch(s, a);
        List<Integer> indicesB = kmpSearch(s, b);

        List<Integer> result = new ArrayList<>();
        if (indicesA.isEmpty() || indicesB.isEmpty()) {
            return result;
        }

        int idxA = 0, idxB = 0;
        while (idxA < indicesA.size()) {
            int i = indicesA.get(idxA);
            
            // Move idxB to the start of the window for i
            while (idxB < indicesB.size() && indicesB.get(idxB) < i - k) {
                idxB++;
            }

            // Check if there's a j in the window [i-k, i+k]
            if (idxB < indicesB.size() && Math.abs(indicesB.get(idxB) - i) <= k) {
                result.add(i);
            }
            
            idxA++;
        }
        return result;
    }

    private List<Integer> kmpSearch(String text, String pattern) {
        List<Integer> occurrences = new ArrayList<>();
        int n = text.length(), m = pattern.length();
        if (m == 0) return occurrences;
        if (n < m) return occurrences;

        int[] lps = computeLPS(pattern);
        int i = 0, j = 0;
        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if (j == m) {
                occurrences.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 occurrences;
    }

    private int[] computeLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int length = 0;
        int i = 1;
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}
```
### Algorithm
- Use an efficient string searching algorithm like KMP (Knuth-Morris-Pratt) to find all occurrences of `a` and `b` in `s`. This populates `indicesA` and `indicesB` in O(N) time.
- Initialize an empty list `result`.
- Use a two-pointer approach. Initialize one pointer `idxA` to 0 for `indicesA` and another pointer `idxB` to 0 for `indicesB`.
- Iterate with `idxA` through `indicesA`. For each index `i = indicesA.get(idxA)`:
  - Advance the `idxB` pointer as long as `indicesB.get(idxB)` is too small (i.e., `indicesB.get(idxB) < i - k`). This brings `idxB` to the beginning of the valid window for `i`.
  - After advancing `idxB`, check if `idxB` is within the bounds of `indicesB` and if the current `j = indicesB.get(idxB)` satisfies `|i - j| <= k`.
  - If it does, `i` is a beautiful index, so add it to `result`.
  - Increment `idxA` to check the next potential beautiful index.
- Since both `idxA` and `idxB` only move forward, this check is done in a single pass over the index lists.
- 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

```