Find beautiful indices in the given array i

Two Pointers String Binary Search Rolling Hash String Matching Hash Function

40.6% acceptance

Feb 25, 2026

204

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn beautiful_indices(s: String, a: String, b: String, k: i32) -> Vec<i32> {
    let s = s.as_bytes();
    let a = a.as_bytes();
    let b = b.as_bytes();
    let k = k as usize;
    let a_pos: Vec<usize> = if a.len() > s.len() { vec![] } else {
      (0..=s.len() - a.len())
        .filter(|&i| &s[i..i + a.len()] == a).collect()
    };
    let b_pos: Vec<usize> = if b.len() > s.len() { vec![] } else {
      (0..=s.len() - b.len())
        .filter(|&i| &s[i..i + b.len()] == b).collect()
    };
    let mut res = vec![];
    let mut j = 0usize;
    for &i in &a_pos {
      while j < b_pos.len() && b_pos[j] + k < i { j += 1; }
      if j < b_pos.len() && b_pos[j] <= i + k { res.push(i as i32); }
    }
    res
  }
}