1930. Unique Length-3 Palindromic Subsequences

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.

Approach 01:

#include <string>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int countPalindromicSubsequence(string inputString) {
        int stringLength = inputString.size();
        int palindromicCount = 0;

        // Return 0 if the string has fewer than 3 characters
        if (stringLength < 3) {
            return palindromicCount;
        }

        // Iterate over each possible middle character
        for (int middleIndex = 0; middleIndex < 26; ++middleIndex) {
            char middleChar = 'a' + middleIndex;  // Map index to character
            size_t leftIndex = inputString.find(middleChar);  // First occurrence of middleChar
            size_t rightIndex = inputString.rfind(middleChar);  // Last occurrence of middleChar

            // Check if the character forms a valid palindrome structure
            if (leftIndex != string::npos && rightIndex != string::npos && leftIndex < rightIndex) {
                unordered_set<char> uniqueCharsBetween(
                    inputString.begin() + leftIndex + 1,
                    inputString.begin() + rightIndex
                );
                palindromicCount += uniqueCharsBetween.size();
            }
        }

        return palindromicCount;
    }
};

class Solution:
    def countPalindromicSubsequence(self, inputString: str) -> int:
        stringLength = len(inputString)
        palindromicCount = 0

        # Return 0 if the string has fewer than 3 characters
        if stringLength < 3:
            return palindromicCount

        # Iterate over each possible middle character
        for middleIndex in range(26):
            middleChar = chr(middleIndex + ord('a'))  # Map index to character
            leftIndex = inputString.find(middleChar)  # First occurrence of middleChar
            rightIndex = inputString.rfind(middleChar)  # Last occurrence of middleChar

            # Check if the character forms a valid palindrome structure
            if leftIndex != -1 and rightIndex != -1 and leftIndex < rightIndex:
                uniqueCharsBetween = set(inputString[leftIndex + 1:rightIndex])  # Unique chars between left and right
                palindromicCount += len(uniqueCharsBetween)

        return palindromicCount

Time Complexity:

• Outer Loop:
  • The outer loop runs 26 times, iterating over each possible character from ‘a’ to ‘z’.
• String Traversals:
  • For each character, the algorithm uses find and rfind operations, which each take \( O(n) \), where \( n \) is the length of the string.
  • If the character forms a valid palindrome structure, extracting unique characters between two indices involves traversing a substring, which can take \( O(n) \) in the worst case.
• Overall Time Complexity:

  \( O(26 \times n) = O(n) \), since the constant factor 26 does not affect asymptotic complexity.

Space Complexity:

• Auxiliary Data Structures:
  • The algorithm uses an unordered set to store unique characters between two indices, which can hold at most 26 characters (the size of the alphabet). This requires \( O(1) \) space in terms of the size of the input.
• Overall Space Complexity:

  \( O(1) \), as the additional space usage is independent of the input size \( n \).