Total appeal of a string

Hash Table String Dynamic Programming

56.4% acceptance

Feb 25, 2026

1218

The appeal of a string is the number of distinct characters found in the string. For example, the appeal of "abbca" is 3 because it has 3 distinct characters: 'a', 'b', and 'c'. Given a string s, return the total appeal of all of its substrings. A substring is a contiguous sequence of characters within a string.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn appeal_sum(s: String) -> i64 {
    let mut last = [-1i64; 26];
    let mut dp = 0i64; // sum of appeal for all substrings ending at current index
    let mut total = 0i64;
    for (i, b) in s.bytes().enumerate() {
      let c = (b - b'a') as usize;
      dp += i as i64 - last[c];
      last[c] = i as i64;
      total += dp;
    }
    total
  }
}