In this guide, you will get 1930. Unique Length-3 Palindromic Subsequences LeetCode Solution with the best time and space complexity. The solution to Unique Length- Palindromic Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Unique Length- 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”)
3 <= s.length <= 105
s consists of only lowercase English letters.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(26) = O(1)
1930. Unique Length-3 Palindromic Subsequences LeetCode Solution in C++
class Solution {
public:
int countPalindromicSubsequence(string s) {
int ans = 0;
vector<int> first(26, s.length());
vector<int> last(26, -1);
for (int i = 0; i < s.length(); ++i) {
const int index = s[i] - 'a';
first[index] = min(first[index], i);
last[index] = i;
}
for (int i = 0; i < 26; ++i)
if (first[i] < last[i])
ans += unordered_set<int>(s.begin() + first[i] + 1, s.begin() + last[i])
.size();
return ans;
}
}; /* code provided by PROGIEZ */
1930. Unique Length-3 Palindromic Subsequences LeetCode Solution in Java
class Solution {
public int countPalindromicSubsequence(String s) {
int ans = 0;
int[] first = new int[26];
int[] last = new int[26];
Arrays.fill(first, s.length());
Arrays.fill(last, -1);
for (int i = 0; i < s.length(); ++i) {
final int index = s.charAt(i) - 'a';
first[index] = Math.min(first[index], i);
last[index] = i;
}
for (int i = 0; i < 26; ++i)
if (first[i] < last[i])
ans += s.substring(first[i] + 1, last[i]).chars().distinct().count();
return ans;
}
} // code provided by PROGIEZ
1930. Unique Length-3 Palindromic Subsequences LeetCode Solution in Python
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
ans = 0
first = [len(s)] * 26
last = [-1] * 26
for i, c in enumerate(s):
index = ord(c) - ord('a')
first[index] = min(first[index], i)
last[index] = i
for f, l in zip(first, last):
if f < l:
ans += len(set(s[f + 1:l]))
return ans # code by PROGIEZ
