problem

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".

 

Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")

Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")

 

Constraints:

  • 3 <= s.length <= 105
  • s consists of only lowercase English letters.

submission

impl Solution {
    pub fn count_palindromic_subsequence(s: String) -> i32 {
        // custom binary search for upper/lower bound
        fn search(range: &[usize], mut f: impl FnMut(usize) -> bool) -> usize {
            let (mut l, mut r) = (0, range.len());
            while l < r {
                let mid = l + (r - l) / 2;
                if !f(range[mid]) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            l
        }
        // collect indices of each different char
        let mut indices = vec![vec![]; 26];
        s.bytes()
            .enumerate()
            .for_each(|(idx, byte)| {
                indices[(byte - b'a') as usize].push(idx);
            });
        let mut ans = 0;
        for i in 0..26 {
            let Some((&first, &last)) = indices[i].first()
                .zip(indices[i].last()) else {
                continue;
            };
            for j in 0..26 {
                // search upper bound of first and lower bound of last
                // upper/lower bound make no difference if i != j
                // however when i == j, we want 3 identical char
                // which means we are search a indice larger than
                // first and less than last
                let l = search(&indices[j], |idx| idx > first);
                let r = search(&indices[j], |idx| idx >= last);
                // first == last means we can't have palindrome
                // we delay the first != last check to make our
                // code shorter
                // i == j && l == r, we search 'xxx', and there are
                // only 2 x in the whole string
                // i != j && l == r, we search 'xyx', either there are
                // no y or there exist y but not between the 2 x
                if first != last && l != r {
                    ans += 1;
                }
            }
        }
        ans
    }
}