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:

1
2
3
4
5
6

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:

1
2
3

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

1
2
3
4
5
6
7

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.

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Brute Force

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

To solve the problem of finding the number of unique palindromes of length three that are subsequences of a given string s, we can follow these steps:

  1. Identify Potential Palindromes: All palindromes of length 3 are of the form “aba”, “cac”, etc. This means the first and third character must be the same.
  2. Track Occurrences: Use a set data structure to keep track of unique palindromic subsequences.
  3. Traverse the String: Use three nested loops to traverse the string and check all combinations of triplets that could form such palindromic patterns.
  4. Check and Store: For each triplet (i, j, k), check if it forms a palindrome, and if so, store it in the set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public class Solution {
    public int countPalindromicSubsequence(String s) {
        Set<String> palindromes = new HashSet<>();
        int n = s.length();
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (s.charAt(i) == s.charAt(k)) {
                        palindromes.add("" + s.charAt(i) + s.charAt(j) + s.charAt(k));
                    }
                }
            }
        }
        
        return palindromes.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        palindromes: set[str] = set()
        n: int = len(s)
        
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    if s[i] == s[k]:
                        palindromes.add(s[i] + s[j] + s[k])
        
        return len(palindromes)

Complexity

  • ⏰ Time complexity: O(n^3)
  • 🧺 Space complexity: O(26^2) = O(1)`

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

Here are points to note:

  1. Character Constraints: Since we only have 26 possible characters (a to z), this problem can be solved in O(26*n) OR O(n).
  2. Palindrome Structure: For a palindrome of length three like aba, aca, etc., the first and last characters must be the same.
  3. First and Last Occurrences: By finding the first and last occurrences of each character, you can identify the range in which potential palindromes might exist.
    • So, we find first and last occurence of each character and store it in hashmap or in this case in 26 char arrays - firstIndex and lastIndex
    • The, we will loop from characters a to z, and for each character from ‘a’ to ‘z’, if it appears more than once (i.e., firstIdx[i] < lastIdx[i]), count the distinct characters between its first and last occurrences.

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.

  • First occurrence of ‘a’: index 0, Last occurrence: index 5
  • Characters between first and last occurrence of ‘a’: bcb
  • Unique characters: ‘b’ and ‘c’ => 2 palindromes: aba, aca
  • For ‘b’: firstIndex = 1, lastIndex = 4, and unique between: cb
  • Unique characters: ‘b’ and ‘c’ => 2 palindromes: bcb, bab

![[unique-length-3-palindromic-subsequences-problem-viz.excalidraw]]

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int countPalindromicSubsequence(String s) {
        int[] firstIdx = new int[26], lastIdx = new int[26];
        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;
        }
        int ans = 0;
        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;        
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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) = O(27n) = O(n)
    • 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.