1930. Unique Length-3 Palindromic Subsequences

Description

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.

 

Solutions

Solution: Hash Table

• Time complexity: O(n*26)
• Space complexity: O(26)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const countPalindromicSubsequence = function (s) {
  const BASE_CHAR_CODE = 'a'.charCodeAt(0);
  let result = 0;

  for (let code = 0; code < 26; code++) {
    const char = String.fromCharCode(BASE_CHAR_CODE + code);
    const start = s.indexOf(char);

    if (start === -1) continue;
    const end = s.lastIndexOf(char);

    if (start >= end) continue;
    const isVisited = Array.from({length: 26}).fill(false);
    let count = 0;

    for (let index = start + 1; index < end; index++) {
      const charCode = s.charCodeAt(index) - BASE_CHAR_CODE;

      if (isVisited[charCode]) continue;
      count += 1;
      isVisited[charCode] = true;
    }
    result += count;
  }
  return result;
};