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

Examples

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

Solution

Method 1 - Brute Force

We need set to store the result, as subsequences must be unique.

We loop on string, check if subsequence is palindrome, and then add it to result.

Method 2 - Using Input Constraint of Only Letters [a-z] Allowed

As we have only 26 chars allowed, this problem can be solved in O(26*n) OR O(n). For 3 letter palindromes, center letter can be anything, but side letters should match. So, palindrome will be like aba.

We will loop from a to z. We track the first and last occurence of each character. Then, for each character, we count unique characters between its first and last occurence. That is the number of palindromes with that character in the first and last positions.

Example: abcbba, we have two unique chars between first and last a (c and b), and two - between first and last b (b and c). No characters in between c so it forms no palindromes.

Code

Java
Using Stream Distinct and Count
public int countPalindromicSubsequence(String s) {
	int firstIdx[] = new int[26], lastIdx[] = new int[26], ans = 0;
	Arrays.fill(firstIdx, Integer.MAX_VALUE);
	for (int i = 0; i < s.length(); ++i) {
		firstIdx[s.charAt(i) - 'a'] = Math.min(firstIdx[s.charAt(i) - 'a'], i);
		lastIdx[s.charAt(i) - 'a'] = i;
	}
	for (int i = 0; i < 26; ++i) {
		if (firstIdx[i] < lastIdx[i]) {
			ans += s.substring(firstIdx[i] + 1, lastIdx[i]).chars().distinct().count();
		}
	}
	return ans;        
}
Using HashSet
public int countPalindromicSubsequence(String s) {
    int first[] = new int[26], last[] = new int[26];
    Arrays.fill(first, Integer.MAX_VALUE);
    for (int i = 0; i < s.length(); ++i) {
        first[s.charAt(i) - 'a'] = Math.min(first[s.charAt(i) - 'a'], i);
        last[s.charAt(i) - 'a'] = i;
    }

	int ans = 0;
	HashSet<Character> set = new HashSet<>();

    for (int i = 0; i < 26; ++i){
        if (first[i] < last[i]){
	        ans += s.substring(first[i] + 1, last[i]).chars().distinct().count();
        }
    }

    return res;
}
Python
class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        first_idx = [float('inf')] * 26
        last_idx = [-float('inf')] * 26
        ans = 0

        for i, char in enumerate(s):
            index = ord(char) - ord('a')
            first_idx[index] = min(first_idx[index], i)
            last_idx[index] = max(last_idx[index], i)

        for i in range(26):
            if first_idx[i] < last_idx[i]:
                unique_chars = set(s[first_idx[i] + 1 : last_idx[i]])
                ans += len(unique_chars)

        return ans

Complexity

  • ⏰ Time complexity: O(n + 26 * m)
    • Traversing the string to fill first and last takes O(n).
    • Checking each character in the alphabet takes constant time O(26).
    • Extracting substrings and counting distinct characters using a set can potentially take O(m) for each valid character, where m is the length of the substring.
  • 🧺 Space complexity: O(n)
    • The space complexity is primarily driven by the space required to store the substrings between the first and last occurrences, which can grow up to O(n). The first and last arrays take constant space O(1) as they have a fixed size of 26.