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

Input: s = "aabca"
Output: 3
Explanation: There are 3 palindromic subsequences of length 3
- "aaa" subsequence of "aabca"
- "aba" subsequence of "aabca"
- "aba" subsequence of "aabca"

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

Constraints:

3 <= s.length <= 105
s consists of only lowercase English letters.

Solution 1 - Check possible 3 letter palindromes with 26 lowercase alphabets by maintaining left and right side characters

The main intution of this approach is that for any given character at i^th index, there are only 26 palindromes possible with length 3, for example if the middle character is 'a' inorder to have a palindrome with length 3, left and right side characters have to be one of the letters from 'a' to 'z', for example aaa, bab... zaz.

In this approach, we are going to use a HashMap, and two HashSets.

We will use HashMap to collect each character from input string s to its count of how many the character have appeared, call it right.
A HashSet to keep track left side elements from current element as we visited through, call it left.
Another HashSet to keep track of unique palindromes, call it unique.

Then, we will loop through each character from input string s:

First, we will decrement the element count from the HashMap right, this is because we are going to consider this as centered element of palindrome and we are moving towards right, and if the count had become 0 then we will remove it from map.
Then, for each letter from a to z, check if same letter appeared in both left HashSet and right HashMap, this means we have found a palindrome. So, add it to unique HashSet.
At the end add current element to left HashSet as we are moving towards right, and the current will become left side element for subsequent elements.
At the end, return number of elements stored inside unique HashSet, these are the unique palindromic subsequences with length 3.

Example:

Lets look at an example with s = "aabca".

First, lets add the characters of input string s into a HashMap (right) with their count of how many times each letter have appeared, so the map will looks like this:

Character	Count
a	3
b	1
c	1

And we also create a HashSet (left) to keep track of left side elements as we pass through. Initially it will be empty.

Now, for each letter in input string s, first will decrement the count from the right map, then from letters a to z check if same letters is in both left as well as right.

When we are at index 0, we will decrement the count of 'a' from the map, and since there are no letters on left side (left set is empty), there will not be any palindromes with length 3, so we will add current element to the left and continue.

right

HashMap and left HashSet will look like this.

right
Character	Count
a	2
b	1
c	1

left
Left character
a

When we are at index 1, we will decrement the count of 'a' from the map, now the left set has a letter a and the same letter present on right map as well, so a palindrome is found aaa, and we will add current element to the left and continue.

right

HashMap and left HashSet will look like this.

right
Character	Count
a	1
b	1
c	1

left
Left character
a

When we are at index 2, we will decrement the count of 'b' from the map, now the left set has a letter a and the same letter present on right map as well, so a palindrome is found aba, and we will add current element to the left and continue.

right

HashMap and left HashSet will look like this.

right
Character	Count
a	1
c	1

left
Left character
a
b

When we are at index 3, we will decrement the count of 'c' from the map, now the left set has a letter a and the same letter present on right map as well, so a palindrome is found aca, left set has letter 'b' but the same letter is not in the right map, so a palindrome is not possible with the letter 'b' from left. We will add current element to the left and continue.

right

HashMap and left HashSet will look like this.

right
Character	Count
a	1

left
Left character
a
b
c

When we are at index 4, we will decrement the count of 'a' from the map, now the left set has letters, but the right map had become empty, so no palindromes are possible with length 3 at this index.
right HashMap and left HashSet will look like this.

Finally, we will return our answer as 3, since we have found 3 unique palindromes with length 3.

In the above implementation, for every character we have looped through from a to z, if you are looking for bit more optimization here, we can just loop through left HashSet itself, at most it will have 26 characters or less.

import java.util.HashMap; import java.util.HashSet; public class UniqueLength3PalindromicSubsequence { static int countPalindromicSubsequence(String s) { // First count each letter occurrence and its count HashMap<Character, Integer> right = new HashMap<>(); for(char c: s.toCharArray()) { right.merge(c, 1, Integer::sum); } HashSet<Character> left = new HashSet<>(); HashSet<String> uniquePalindromes = new HashSet<>(); // now loop through every character of string and check if left and right side characters are same for(char c: s.toCharArray()) { int newCount = right.merge(c, -1, Integer::sum); if(newCount == 0) { right.remove(c); } for(Character leftChar: left) { if(right.containsKey(leftChar)) { // this is a palindrome uniquePalindromes.add(String.valueOf(c) +leftChar);// just adding 2 letters, // as left and right letters will be same // in 3 letters palindromes } } left.add(c); } return uniquePalindromes.size(); } public static void main(String[] args) { System.out.println(countPalindromicSubsequence("aabca")); System.out.println(countPalindromicSubsequence("adc")); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s (for every character, we are looping thorugh lowercase alphabets 26, since this is constant number we can ignore it).
Space complexity: O(n)

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Example:

Complexity Analysis: