Coding Daily

Problem Description

Given a string s, return the number of unique palindromic subsequences of length three. A palindrome reads the same forwards and backwards, and a subsequence is a sequence that can be derived from the string by deleting some or no elements without changing the order of the remaining elements.

Example:

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

Solution Code

class Solution {
    public int countPalindromicSubsequence(String s) {
        int[] firstOccurrence = new int[26];
        int[] lastOccurrence = new int[26];
        Arrays.fill(firstOccurrence, -1);
        Arrays.fill(lastOccurrence, -1);
        
        // Record the first and last occurrence of each character
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (firstOccurrence[c - 'a'] == -1) {
                firstOccurrence[c - 'a'] = i;
            }
            lastOccurrence[c - 'a'] = i;
        }
        
        int count = 0;
        // For each character, count the unique characters between its first and last occurrence
        for (int i = 0; i < 26; i++) {
            if (firstOccurrence[i] != -1 && lastOccurrence[i] != -1 && firstOccurrence[i] < lastOccurrence[i]) {
                boolean[] uniqueChars = new boolean[26];
                for (int j = firstOccurrence[i] + 1; j < lastOccurrence[i]; j++) {
                    uniqueChars[s.charAt(j) - 'a'] = true;
                }
                for (boolean b : uniqueChars) {
                    if (b) count++;
                }
            }
        }
        
        return count;
    }
}

Approach Name

Two-Pass with First and Last Occurrence Tracking

Intuition

The key insight is that for a palindrome of length three, the first and last characters must be the same, and the middle character can be any character that appears between the first and last occurrence of the outer characters. By tracking the first and last occurrence of each character in the string, we can efficiently count the number of unique middle characters that can form valid palindromic subsequences.

Algorithm

First and Last Occurrence Tracking:
- Use two arrays, firstOccurrence and lastOccurrence, to store the first and last indices of each character in the string.
- Iterate through the string to populate these arrays.
Counting Unique Middle Characters:
- For each character, if it has both a first and last occurrence, and the first occurrence is before the last occurrence, then there is at least one valid palindromic subsequence.
- Use a boolean array to track unique characters that appear between the first and last occurrence of the current character.
- Count the number of unique characters in this range.
Return the Count:
- The total count of unique palindromic subsequences is the sum of unique middle characters for all valid outer characters.

Complexity Analysis

Time Complexity: O(n), where n is the length of the string. We perform two passes through the string: one to record the first and last occurrences, and another to count unique middle characters.
Space Complexity: O(1), since we use a fixed amount of extra space (two arrays of size 26 and a boolean array of size 26).

Hard - 2484. Count Palindromic Subsequences

Basic - 703532. Last index of a character in the string Related Articles: Find last index of a character in the string

2484. Unique Length-3 Palindromic Subsequences