Find beautiful indices in the given array ii

Two Pointers String Binary Search Rolling Hash String Matching Hash Function

27.6% acceptance

Feb 25, 2026

208

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_pos = Self::kmp_find(s, a.as_bytes());
    let b_pos = Self::kmp_find(s, b.as_bytes());
    let k = k as usize;
    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
  }

  fn kmp_find(text: &[u8], pat: &[u8]) -> Vec<usize> {
    let m = pat.len();
    if m == 0 { return vec![]; }
    let mut fail = vec![0usize; m];
    let mut k = 0usize;
    for i in 1..m {
      while k > 0 && pat[k] != pat[i] { k = fail[k - 1]; }
      if pat[k] == pat[i] { k += 1; }
      fail[i] = k;
    }
    let mut res = vec![];
    k = 0;
    for (i, &c) in text.iter().enumerate() {
      while k > 0 && pat[k] != c { k = fail[k - 1]; }
      if pat[k] == c { k += 1; }
      if k == m { res.push(i + 1 - m); k = fail[k - 1]; }
    }
    res
  }
}