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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    
    
    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

1
2
3
4
5
6
7
8
9


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

Solution

Method 1 – Rolling Hash and Two Pointers (Optimized for Large Input)

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. Since s can be very large, we use direct string matching to find all start indices of a and b, 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. Both lists are naturally sorted.
  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 in sorted order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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.