3008. Find Beautiful Indices in the Given Array II Solution

Q: Is Find Beautiful Indices in the Given Array II easy or hard?

Find Beautiful Indices in the Given Array II is classified as Hard. The difficulty comes from combining efficient substring detection with a linear-time verification strategy. Recognizing that the problem reduces to scanning two sorted lists of indices is the key insight.

Q: Find Beautiful Indices in the Given Array II Python/Java solution

Python and Java implementations typically compute all match positions of a and b, store them in lists, and then apply a two-pointer scan to check the k-distance condition. The logic is identical across languages and runs in O(n) time with O(n) space.

Q: How to solve Find Beautiful Indices in the Given Array II in O(n)?

First detect every occurrence of a and b using rolling hash or another linear string matching technique. Store their starting indices in two arrays. Then iterate through the a indices while advancing a pointer over the b indices so that only indices within the range [i−k, i+k] are considered. Each pointer moves forward once, giving O(n) complexity.

Q: What is the best approach for Find Beautiful Indices in the Given Array II?

The optimized two-pass scan is the most efficient approach. First collect all indices where substring a and substring b appear using linear string matching. Then use a two-pointer sweep to check whether any b index lies within k distance of each a index. This keeps the total time complexity O(n).

Q: Is Find Beautiful Indices in the Given Array II asked at Google/Amazon/Meta?

Problems involving substring matching, rolling hash, and two-pointer scans frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine pattern matching with distance constraints are common in senior-level string processing questions.

Q: What data structure is used in Find Beautiful Indices in the Given Array II?

The solution primarily uses arrays or lists to store occurrence indices of the substrings. Two pointers are then used to scan those sorted lists efficiently. Some implementations also use rolling hash structures to detect substring matches quickly.

Q: What is the time complexity of Find Beautiful Indices in the Given Array II?

The optimal solution runs in O(n) time where n is the length of the string. One pass finds occurrences of substrings a and b, and another linear scan with two pointers verifies the distance condition. The space complexity is O(n) for storing occurrence indices.

The 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 * 10⁵
1 <= a.length, b.length <= 5 * 10⁵
s, a, and b contain only lowercase English letters.

Approach overview

Problem Overview: Given a string s and two patterns a and b, return all indices i where a appears in s and there exists an index j where b appears such that |i - j| ≤ k. The output must be sorted and include every valid starting index of a.

The core challenge is efficiently locating all occurrences of both substrings and quickly verifying whether any occurrence of b lies within distance k from each occurrence of a. Naively comparing every pair of indices would be too slow for large inputs, so efficient string matching and range checking are required.

Approach 1: Sliding Window with Hash Map (O(n) time, O(n) space)

First locate all occurrences of a and b in s. Efficient substring detection can be done using a rolling hash or other string matching techniques so each position is checked in constant time. Store all indices where b appears in a hash-based structure or array. Then iterate through each index where a occurs and maintain a sliding window representing the valid range [i - k, i + k]. If any stored b index falls inside that window, the index i is beautiful.

The hash-backed lookup helps quickly verify candidate positions while scanning forward. This approach works well when substring matches are already computed using a rolling hash and you want a straightforward window-based validation. Time complexity is O(n) after preprocessing and space complexity is O(n) for storing match indices.

Approach 2: Optimized Two-Pass Scan (O(n) time, O(n) space)

This approach separates the problem into two clean passes. First scan the string and record every starting index of a and b. Rolling hash or other linear-time matching ensures this step remains efficient. Once both index lists are built, process them with a two pointers technique.

Maintain a pointer on the list of b indices while iterating through each index of a. Move the pointer until the b index is within the left boundary i - k. Then check whether the current b index is ≤ i + k. Because both lists are sorted by construction, the pointer never moves backward, producing a linear pass over both lists. This eliminates repeated searches and avoids using binary search.

The two-pass strategy is typically the fastest and easiest to reason about. Each list is scanned once, so the total complexity stays O(n) with O(n) extra space for storing indices.

Recommended for interviews: The optimized two-pass scan is what interviewers usually expect. It shows that you first reduce the problem to two lists of substring matches and then apply a linear two-pointer sweep to check distance constraints efficiently. Mentioning a brute-force pair comparison demonstrates baseline understanding, but implementing the linear scan highlights algorithmic maturity and awareness of scalable string-processing techniques.

Approach 1: Sliding Window with Hash Map

This approach leverages a sliding window technique along with a hash map to efficiently solve the problem. First, we iterate through the string 's' and look for occurrences of string 'b' and store their indices in a hash map. We then perform a second pass to identify all starting positions of string 'a'. For each such position, we check within the range defined by 'k' in the hash map if there's an occurrence of 'b' that satisfies all conditions for that specific position to be considered beautiful.

Python

def find_beautiful_indices(s, a, b, k):
    n = len(s)
    alen, blen = len(a), len(b)
    result = []

    # Collect all indices where b is found
    b_indices = [i for i in range(n - blen + 1) if s[i:i + blen] == b]

    for i in range(n - alen + 1):
        if s[i:i + alen] == a:
            # Check any b index in range
            if any(abs(i - j) <= k for j in b_indices):
                result.append(i)

    return result

# Usage
# result = find_beautiful_indices(s, a, b, k)
# for index in result:  # use index

Java

import java.util.*;

public class Main {
    public static List<Integer> findBeautifulIndices(String s, String a, String b, int k) {
        int n = s.length(), alen = a.length(), blen = b.length();
        List<Integer> result = new ArrayList<>();
        List<Integer> bIndices = new ArrayList<>();

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

        for (int i = 0; i <= n - alen; i++) {
            if (s.substring(i, i + alen).equals(a)) {
                for (int j : bIndices) {
                    if (Math.abs(j - i) <= k) {
                        result.add(i);
                        break;
                    }
                }
            }
        }

        return result;
    }

    // Usage
    // List<Integer> result = findBeautifulIndices(s, a, b, k);
    // for (int index : result) { /* use index */ }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

vector<int> findBeautifulIndices(const string& s, const string& a, const string& b, int k) {
    int n = s.length(), alen = a.length(), blen = b.length();
    vector<int> result;
    vector<int> b_indices;

    for (int i = 0; i <= n - blen; ++i) {
        if (s.substr(i, blen) == b) {
            b_indices.push_back(i);
        }
    }

    for (int i = 0; i <= n - alen; ++i) {
        if (s.substr(i, alen) == a) {
            for (int j : b_indices) {
                if (abs(j - i) <= k) {
                    result.push_back(i);
                    break;
                }
            }
        }
    }

    return result;
}

// Usage
// vector<int> result = findBeautifulIndices(s, a, b, k);
// for (int index : result) { /* use index */ }

JavaScript

function findBeautifulIndices(s, a, b, k) {
    let n = s.length, alen = a.length, blen = b.length;
    let result = [];
    let bIndices = [];

    for (let i = 0; i <= n - blen; i++) {
        if (s.substring(i, i + blen) === b) {
            bIndices.push(i);
        }
    }

    for (let i = 0; i <= n - alen; i++) {
        if (s.substring(i, i + alen) === a) {
            if (bIndices.some(j => Math.abs(j - i) <= k)) {
                result.push(i);
            }
        }
    }

    return result;
}

// Usage
// let result = findBeautifulIndices(s, a, b, k);
// result.forEach(index => { /* use index */ });

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int* findBeautifulIndices(char* s, char* a, char* b, int k, int* returnSize) {
    int n = strlen(s), alen = strlen(a), blen = strlen(b);
    int* indices = (int*)malloc((n+1) * sizeof(int));
    *returnSize = 0;

    int* b_indices = (int*)malloc(n * sizeof(int));
    int b_count = 0;

    for (int i = 0; i <= n - blen; ++i) {
        if (strncmp(s + i, b, blen) == 0) {
            b_indices[b_count++] = i;
        }
    }

    for (int i = 0; i <= n - alen; ++i) {
        if (strncmp(s + i, a, alen) == 0) {
            for (int j = 0; j < b_count; ++j) {
                if (abs(b_indices[j] - i) <= k) {
                    indices[(*returnSize)++] = i;
                    break;
                }
            }
        }
    }

    free(b_indices);
    return indices;
}

// Usage:
// int resultSize;
// int* result = findBeautifulIndices(s, a, b, k, &resultSize);
// for(int i = 0; i < resultSize; i++) { /* use result[i] */ }
// free(result);

using System;
using System.Collections.Generic;

public class Solution {
    public List<int> FindBeautifulIndices(string s, string a, string b, int k) {
        int n = s.Length, alen = a.Length, blen = b.Length;
        List<int> result = new List<int>();
        List<int> bIndices = new List<int>();

        for (int i = 0; i <= n - blen; i++) {
            if (s.Substring(i, blen) == b) {
                bIndices.Add(i);
            }
        }

        for (int i = 0; i <= n - alen; i++) {
            if (s.Substring(i, alen) == a) {
                foreach (int j in bIndices) {
                    if (Math.Abs(j - i) <= k) {
                        result.Add(i);
                        break;
                    }
                }
            }
        }

        return result;
    }

    // Usage
    // var result = new Solution().FindBeautifulIndices(s, a, b, k);
    // foreach (int index in result) { /* use index */ }
}

In this Python solution, list comprehensions and the 'any()' function are used for conciseness. After finding all the positions of 'b', each position of 'a' is checked against these indices to see if the distance criterion is satisfied, confirming its beauty.

Complexity

The time complexity is O(n) and the space complexity is O(m). 'n' refers to the length of 's', and 'm' refers to the number of times 'b' appears in 's'.

Try this approach in the editor

Approach 2: Optimized Two-Pass Scan

In this approach, we perform a two-pass scan over the string 's'. During the first pass, we identify all starting positions of the string 'a'. Simultaneously, we maintain the closest positions of string 'b' in a separate array so that for each position of 'a', we can check efficiently in constant time if there exists a position of 'b' that satisfies the distance condition. This method ensures each index checks only once, optimizing both speed and additional storage.

Python

def find_beautiful_indices_optimized(s, a, b, k):
    n = len(s)
    alen, blen = len(a), len(b)
    result = []

    closest_b = [-1] * n
    last_b = -1
    
    for i in range(n):
        if i >= blen - 1 and s[i-blen+1:i+1] == b:
            last_b = i - blen + 1
        closest_b[i] = last_b

    for i in range(n - alen + 1):
        if s[i:i + alen] == a:
            left_limit = max(0, i - k)
            right_limit = min(n - 1, i + k)
            for j in range(left_limit, right_limit + 1):
                if closest_b[j] != -1 and abs(closest_b[j] - i) <= k:
                    result.append(i)
                    break

    return result

# Usage
# result = find_beautiful_indices_optimized(s, a, b, k)
# for index in result:  # use index

Java

import java.util.*;

public class Main {
    public static List<Integer> findBeautifulIndicesOptimized(String s, String a, String b, int k) {
        int n = s.length(), alen = a.length(), blen = b.length();
        List<Integer> result = new ArrayList<>();
        int[] closest_b = new int[n];
        Arrays.fill(closest_b, -1);
        int last_b = -1;

        for (int i = 0; i <= n - blen; i++) {
            if (s.substring(i, i + blen).equals(b)) {
                last_b = i;
            }
            closest_b[i] = last_b;
        }

        for (int i = 0; i <= n - alen; i++) {
            if (s.substring(i, i + alen).equals(a)) {
                int left_limit = Math.max(0, i - k);
                int right_limit = Math.min(n - 1, i + k);
                for (int j = left_limit; j <= right_limit; j++) {
                    if (closest_b[j] != -1 && Math.abs(closest_b[j] - i) <= k) {
                        result.add(i);
                        break;
                    }
                }
            }
        }

        return result;
    }

    // Usage
    // List<Integer> result = findBeautifulIndicesOptimized(s, a, b, k);
    // for (int index : result) { /* use index */ }
}

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> findBeautifulIndicesOptimized(const string& s, const string& a, const string& b, int k) {
    int n = s.length(), alen = a.length(), blen = b.length();
    vector<int> result;
    vector<int> closest_b(n, -1);
    int last_b = -1;

    for (int i = 0; i <= n - blen; ++i) {
        if (s.substr(i, blen) == b) {
            last_b = i;
        }
        closest_b[i] = last_b;
    }

    for (int i = 0; i <= n - alen; ++i) {
        if (s.substr(i, alen) == a) {
            int left_limit = max(0, i - k);
            int right_limit = min(n - 1, i + k);
            for (int j = left_limit; j <= right_limit; ++j) {
                if (closest_b[j] != -1 && abs(closest_b[j] - i) <= k) {
                    result.push_back(i);
                    break;
                }
            }
        }
    }

    return result;
}

// Usage
// vector<int> result = findBeautifulIndicesOptimized(s, a, b, k);
// for (int index : result) { /* use index */ }

JavaScript

function findBeautifulIndicesOptimized(s, a, b, k) {
    let n = s.length, alen = a.length, blen = b.length;
    let result = [];
    let closest_b = Array(n).fill(-1);
    let last_b = -1;

    for (let i = 0; i <= n - blen; i++) {
        if (s.substring(i, i + blen) === b) {
            last_b = i;
        }
        closest_b[i] = last_b;
    }

    for (let i = 0; i <= n - alen; i++) {
        if (s.substring(i, i + alen) === a) {
            let left_limit = Math.max(0, i - k);
            let right_limit = Math.min(n - 1, i + k);
            for (let j = left_limit; j <= right_limit; j++) {
                if (closest_b[j] !== -1 && Math.abs(closest_b[j] - i) <= k) {
                    result.push(i);
                    break;
                }
            }
        }
    }

    return result;
}

// Usage
// let result = findBeautifulIndicesOptimized(s, a, b, k);
// result.forEach(index => { /* use index */ });

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

int* findBeautifulIndicesOptimized(char* s, char* a, char* b, int k, int* returnSize) {
    int n = strlen(s), alen = strlen(a), blen = strlen(b);
    *returnSize = 0;
    int* result = (int*)malloc((n + 1) * sizeof(int));

    // Precompute last found b index
    int* closest_b = (int*)malloc(n * sizeof(int));
    memset(closest_b, -1, n * sizeof(int));
    int last_b = -1;
    
    for (int i = 0; i < n; ++i) {
        if (i >= blen && strncmp(s + i - blen, b, blen) == 0) {
            last_b = i - blen;
        }
        closest_b[i] = last_b;
    }

    for (int i = 0; i <= n - alen; ++i) {
        if (strncmp(s + i, a, alen) == 0) {
            int left_limit = i - k > 0 ? i - k : 0;
            int right_limit = i + k < n - 1 ? i + k : n - 1;
            for (int j = left_limit; j <= right_limit; ++j) {
                if (closest_b[j] >= 0 && abs(closest_b[j] - i) <= k) {
                    result[(*returnSize)++] = i;
                    break;
                }
            }
        }
    }

    free(closest_b);
    return result;
}

// Usage:
// int resultSize;
// int* result = findBeautifulIndicesOptimized(s, a, b, k, &resultSize);
// for (int i = 0; i < resultSize; ++i) { /* use result[i] */ }
// free(result);

using System;
using System.Collections.Generic;

public class Solution {
    public List<int> FindBeautifulIndicesOptimized(string s, string a, string b, int k) {
        int n = s.Length, alen = a.Length, blen = b.Length;
        List<int> result = new List<int>();
        int[] closest_b = new int[n];
        Array.Fill(closest_b, -1);
        int last_b = -1;

        for (int i = 0; i <= n - blen; i++) {
            if (s.Substring(i, blen) == b) {
                last_b = i;
            }
            closest_b[i] = last_b;
        }

        for (int i = 0; i <= n - alen; i++) {
            if (s.Substring(i, alen) == a) {
                int left_limit = Math.Max(0, i - k);
                int right_limit = Math.Min(n - 1, i + k);
                for (int j = left_limit; j <= right_limit; j++) {
                    if (closest_b[j] != -1 && Math.Abs(closest_b[j] - i) <= k) {
                        result.Add(i);
                        break;
                    }
                }
            }
        }

        return result;
    }

    // Usage
    // var result = new Solution().FindBeautifulIndicesOptimized(s, a, b, k);
    // foreach (int index in result) { /* use index */ }
}

The optimized Python solution employs a dual-pass methodology to identify and validate positions efficiently. By precomputing locations of 'b', it enables a swift check of potential 'a' starting indices within defined boundaries.

Complexity

This approach's time and space complexity are both O(n) due to sequential access and auxiliary storage for 'b' indices.

Try this approach in the editor

Approach 3: Default Approach

func beautifulIndices(s string, a string, b string, k int) []int {

	s_len := len(s)
	a_len := len(a)
	b_len := len(b)

	final := make([]int, 0)
	lps_a := make([]int, a_len)
	lps_b := make([]int, b_len)
	a_index := make([]int, 0)
	b_index := make([]int, 0)

	var pat func(lps []int, s_l int, pattern string)

	pat = func(lps []int, s_l int, pattern string) {

		l := 0
		lps[0] = 0
		i := 1

		for i < s_l {
			if pattern[i] == pattern[l] {
				l++
				lps[i] = l
				i++
			} else {
				if l != 0 {
					l = lps[l-1]
				} else {
					lps[i] = l
					i++
				}
			}
		}
	}

	pat(lps_a, a_len, a)
	pat(lps_b, b_len, b)

	var kmp func(pat string, pat_l int, lps []int, index *[]int)

	kmp = func(pat string, pat_l int, lps []int, index *[]int) {
		i := 0
		j := 0
		for s_len-i >= pat_l-j {
			if s[i] == pat[j] {
				i++
				j++
			}
			if j == pat_l {
				*index = append(*index, i-pat_l)
				j = lps[j-1]
			} else if s[i] != pat[j] {
				if j != 0 {
					j = lps[j-1]
				} else {
					i++
				}
			}
		}
	}

	kmp(a, a_len, lps_a, &a_index)
	kmp(b, b_len, lps_b, &b_index)

	// fmt.Println(a_index, b_index)

	i := 0
	j := 0

	for i < len(a_index) && j < len(b_index) {
		if a_index[i]+k >= b_index[j] && a_index[i]-k <= b_index[j] {
			final = append(final, a_index[i])
			i++
		} else if a_index[i]-k > b_index[j] {
			j++
		} else {
			i++
		}
	}

	return final
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sliding Window with Hash Map	The time complexity is O(n) and the space complexity is O(m). 'n' refers to the length of 's', and 'm' refers to the number of times 'b' appears in 's'.
Optimized Two-Pass Scan	This approach's time and space complexity are both O(n) due to sequential access and auxiliary storage for 'b' indices.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Sliding Window with Hash Map	O(n)	O(n)	When substring matches are tracked using hashing or rolling hash and you want simple window-based validation.
Optimized Two-Pass Scan	O(n)	O(n)	Best general solution. Uses two pointers over sorted occurrence lists for linear verification.

Frequently asked questions

Is Find Beautiful Indices in the Given Array II easy or hard?

Find Beautiful Indices in the Given Array II is classified as Hard. The difficulty comes from combining efficient substring detection with a linear-time verification strategy. Recognizing that the problem reduces to scanning two sorted lists of indices is the key insight.

Find Beautiful Indices in the Given Array II Python/Java solution

Python and Java implementations typically compute all match positions of a and b, store them in lists, and then apply a two-pointer scan to check the k-distance condition. The logic is identical across languages and runs in O(n) time with O(n) space.

How to solve Find Beautiful Indices in the Given Array II in O(n)?

First detect every occurrence of a and b using rolling hash or another linear string matching technique. Store their starting indices in two arrays. Then iterate through the a indices while advancing a pointer over the b indices so that only indices within the range [i−k, i+k] are considered. Each pointer moves forward once, giving O(n) complexity.

What is the best approach for Find Beautiful Indices in the Given Array II?

The optimized two-pass scan is the most efficient approach. First collect all indices where substring a and substring b appear using linear string matching. Then use a two-pointer sweep to check whether any b index lies within k distance of each a index. This keeps the total time complexity O(n).

Is Find Beautiful Indices in the Given Array II asked at Google/Amazon/Meta?

Problems involving substring matching, rolling hash, and two-pointer scans frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine pattern matching with distance constraints are common in senior-level string processing questions.

What data structure is used in Find Beautiful Indices in the Given Array II?

The solution primarily uses arrays or lists to store occurrence indices of the substrings. Two pointers are then used to scan those sorted lists efficiently. Some implementations also use rolling hash structures to detect substring matches quickly.

What is the time complexity of Find Beautiful Indices in the Given Array II?

The optimal solution runs in O(n) time where n is the length of the string. One pass finds occurrences of substrings a and b, and another linear scan with two pointers verifies the distance condition. The space complexity is O(n) for storing occurrence indices.

Find Beautiful Indices in the Given Array II solution and explanation

The problem

Approach overview

Approach 1: Sliding Window with Hash Map

Approach 2: Optimized Two-Pass Scan

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Beautiful Indices in the Given Array II solution and explanation

The problem

Approach overview

Approach 1: Sliding Window with Hash Map

Approach 2: Optimized Two-Pass Scan

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems