Find Beautiful Indices in the Given Array I

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 insorted order from smallest to largest.

Examples

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

Solution

Method 1 – Rolling Hash and Two Pointers

Intuition

We need to find all indices where substring a occurs in s, and for each such index, check if there is any occurrence of substring b within distance k. We can precompute all start indices of a and b in s using rolling hash or direct string matching, then use two pointers to efficiently check the distance condition.

Approach

1. Find all start indices where a occurs in s (call this apos).
2. Find all start indices where b occurs in s (call this bpos).
3. Sort both lists.
4. For each index i in apos, use two pointers to check if there is any j in bpos such that |i - j| <= k.
5. If so, add i to the answer.
6. Return the list of beautiful indices.

Code

C++

class Solution {
public:
    vector<int> beautifulIndices(string s, string a, string b, int k) {
        vector<int> apos, bpos, ans;
        for (int i = 0; i + a.size() <= s.size(); ++i)
            if (s.substr(i, a.size()) == a) apos.push_back(i);
        for (int i = 0; i + b.size() <= s.size(); ++i)
            if (s.substr(i, b.size()) == b) bpos.push_back(i);
        int j = 0;
        for (int i : apos) {
            while (j < bpos.size() && bpos[j] < i - k) ++j;
            int jj = j;
            while (jj < bpos.size() && bpos[jj] <= i + k) {
                ans.push_back(i);
                break;
            }
        }
        return ans;
    }
};

Go

func beautifulIndices(s, a, b string, k int) []int {
    apos, bpos := []int{}, []int{}
    for i := 0; i+len(a) <= len(s); i++ {
        if s[i:i+len(a)] == a { apos = append(apos, i) }
    }
    for i := 0; i+len(b) <= len(s); i++ {
        if s[i:i+len(b)] == b { bpos = append(bpos, i) }
    }
    ans := []int{}
    j := 0
    for _, i := range apos {
        for j < len(bpos) && bpos[j] < i-k { j++ }
        jj := j
        for jj < len(bpos) && bpos[jj] <= i+k {
            ans = append(ans, i)
            break
        }
    }
    return ans
}

Java

class Solution {
    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
        List<Integer> apos = new ArrayList<>(), bpos = new ArrayList<>(), ans = new ArrayList<>();
        for (int i = 0; i + a.length() <= s.length(); i++)
            if (s.substring(i, i + a.length()).equals(a)) apos.add(i);
        for (int i = 0; i + b.length() <= s.length(); i++)
            if (s.substring(i, i + b.length()).equals(b)) bpos.add(i);
        int j = 0;
        for (int i : apos) {
            while (j < bpos.size() && bpos.get(j) < i - k) j++;
            int jj = j;
            while (jj < bpos.size() && bpos.get(jj) <= i + k) {
                ans.add(i);
                break;
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun beautifulIndices(s: String, a: String, b: String, k: Int): List<Int> {
        val apos = mutableListOf<Int>()
        val bpos = mutableListOf<Int>()
        for (i in 0..s.length - a.length) if (s.substring(i, i + a.length) == a) apos.add(i)
        for (i in 0..s.length - b.length) if (s.substring(i, i + b.length) == b) bpos.add(i)
        val ans = mutableListOf<Int>()
        var j = 0
        for (i in apos) {
            while (j < bpos.size && bpos[j] < i - k) j++
            var jj = j
            while (jj < bpos.size && bpos[jj] <= i + k) {
                ans.add(i)
                break
            }
        }
        return ans
    }
}

Python

class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> list[int]:
        apos = [i for i in range(len(s) - len(a) + 1) if s[i:i+len(a)] == a]
        bpos = [i for i in range(len(s) - len(b) + 1) if s[i:i+len(b)] == b]
        ans = []
        j = 0
        for i in apos:
            while j < len(bpos) and bpos[j] < i - k:
                j += 1
            jj = j
            while jj < len(bpos) and bpos[jj] <= i + k:
                ans.append(i)
                break
        return ans

Rust

impl Solution {
    pub fn beautiful_indices(s: String, a: String, b: String, k: i32) -> Vec<i32> {
        let apos: Vec<_> = (0..=s.len()-a.len()).filter(|&i| &s[i..i+a.len()] == a).collect();
        let bpos: Vec<_> = (0..=s.len()-b.len()).filter(|&i| &s[i..i+b.len()] == b).collect();
        let mut ans = vec![];
        let mut j = 0;
        for &i in &apos {
            while j < bpos.len() && bpos[j] < i as i32 - k { j += 1; }
            let mut jj = j;
            while jj < bpos.len() && bpos[jj] <= i as i32 + k {
                ans.push(i as i32);
                break;
            }
        }
        ans
    }
}

TypeScript

class Solution {
    beautifulIndices(s: string, a: string, b: string, k: number): number[] {
        const apos: number[] = [];
        const bpos: number[] = [];
        for (let i = 0; i <= s.length - a.length; i++)
            if (s.substring(i, i + a.length) === a) apos.push(i);
        for (let i = 0; i <= s.length - b.length; i++)
            if (s.substring(i, i + b.length) === b) bpos.push(i);
        const ans: number[] = [];
        let j = 0;
        for (const i of apos) {
            while (j < bpos.length && bpos[j] < i - k) j++;
            let jj = j;
            while (jj < bpos.length && bpos[jj] <= i + k) {
                ans.push(i);
                break;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n + m), where n is the length of s and m is the number of matches. Each index is processed efficiently.
• 🧺 Space complexity: O(n), for storing the positions and result.