Unique length 3 palindromic subsequences

Hash Table String Bit Manipulation Prefix Sum

73.8% acceptance

Feb 25, 2026

2859

108

Given a string s, return the number of unique palindromes of length three that are a subsequence of s. Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once. A palindrome is a string that reads the same forwards and backwards. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde".

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_palindromic_subsequence(s: String) -> i32 {
    let bytes = s.as_bytes();
    let mut count = 0;
    for c in b'a'..=b'z' {
      let first = bytes.iter().position(|&b| b == c);
      let last = bytes.iter().rposition(|&b| b == c);
      if let (Some(f), Some(l)) = (first, last) {
        if l > f + 1 {
          let mut unique = std::collections::HashSet::new();
          for &b in &bytes[f + 1..l] {
            unique.insert(b);
          }
          count += unique.len() as i32;
        }
      }
    }
    count
  }
}