Number of same end substrings

Array Hash Table String Counting Prefix Sum

61.6% acceptance

Mar 31, 2026

You are given a 0-indexed string s, and a 2D array of integers queries, where queries[i] = [li, ri] indicates a substring of s starting from the index li and ending at the index ri (both inclusive), i.e. s[li..ri]. Return an array ans where ans[i] is the number of same-end substrings of queries[i]. A 0-indexed string t of length n is called same-end if it has the same character at both of its ends, i.e., t[0] == t[n - 1]. A substring is a contiguous non-empty sequence of characters within a string.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn same_end_substring_count(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = s.len();
    let bytes = s.as_bytes();
    let mut prefix = vec![[0i32; 26]; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i];
      prefix[i + 1][(bytes[i] - b'a') as usize] += 1;
    }
    queries
      .iter()
      .map(|q| {
        let l = q[0] as usize;
        let r = q[1] as usize;
        let mut total = 0i32;
        for c in 0..26 {
          let freq = prefix[r + 1][c] - prefix[l][c];
          total += freq * (freq + 1) / 2;
        }
        total
      })
      .collect()
  }
}