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 n = s.length;
  const BASE_CODE = 'a'.charCodeAt(0);
  const starts = Array.from({ length: 26 }, () => n);
  const ends = Array.from({ length: 26 }, () => -1);
  let result = 0;

  for (let index = 0; index < n; index++) {
    const code = s[index].charCodeAt(0) - BASE_CODE;

    starts[code] = Math.min(starts[code], index);
    ends[code] = Math.max(ends[code], index);
  }

  for (let code = 0; code < 26; code++) {
    const start = starts[code];
    const end = ends[code];

    if (start === n || end === -1 || start === end) continue;

    const visited = new Array(26).fill(false);

    for (let index = start + 1; index < end; index++) {
      const targetCode = s[index].charCodeAt(0) - BASE_CODE;

      if (visited[targetCode]) continue;

      result += 1;
      visited[targetCode] = true;
    }
  }

  return result;
};