Leetcode 1930: Unique Length-3 Palindromic Subsequences

Input: The input consists of a single string s of length n.

Example: s = "aabca"

Constraints:

• 3 <= s.length <= 10^5

• s consists of only lowercase English letters.

Output: Return the number of unique palindromic subsequences of length 3 that appear in s.

Example: 3

Constraints:

Goal: To efficiently count all unique palindromic subsequences of length 3.

Steps:

• Use a frequency map to track the first and last occurrences of each character in the string.

• For each character, check if it forms a palindromic subsequence with other characters in between.

Goal: The problem needs to efficiently count subsequences for strings as large as 10^5 characters.

Steps:

• The string length will be between 3 and 100,000.

• The string only contains lowercase English letters.

Assumptions:

• All characters in the string are lowercase English letters.

• The string will always have at least 3 characters.

• Input: s = "aabca"

• Explanation: The three unique palindromic subsequences are 'aba', 'aaa', and 'aca', so the output is 3.

Approach: To count the palindromic subsequences, we can use a strategy that involves tracking first and last occurrences of characters and counting the valid subsequences.

Observations:

• The string can be very large, so an efficient solution is needed.

• We need to find a way to count palindromic subsequences without generating all possible subsequences.

Steps:

• Create a map for the first and last occurrences of each character in the string.

• For each character in the string, check if it can form a palindromic subsequence of length 3.

• Count each valid subsequence once.

Empty Inputs:

• If the string has fewer than 3 characters, the result should be 0.

Large Inputs:

• The solution should handle strings up to length 100,000 efficiently.

Special Values:

• If the string consists of only one character repeated, the number of palindromic subsequences could be larger.

Constraints:

• Consider the time complexity to be linear in the size of the string.

int countPalindromicSubsequence(string num) {
    int n = num.size(), res = 0;        
    vector<int> fst(26,n), lst(26,0);
    for(int i = 0; i < n; i++) {
        fst[num[i]-'a']= min(fst[num[i]-'a'], i);
        lst[num[i]-'a'] = i;
    }
    for(int i = 0; i < 26; i++) {
if(fst[i] < lst[i]) res += unordered_set<char>(num.begin() + fst[i] + 1, num.begin() + lst[i]).size();
    }
    return res;        
}

1 : Function Header

int countPalindromicSubsequence(string num) {

Defines the function `countPalindromicSubsequence`, which takes a string `num` and returns an integer representing the count of distinct palindromic subsequences.

2 : Variable Initialization

    int n = num.size(), res = 0;

Initializes `n` to the length of the string `num` and `res` to store the count of palindromic subsequences.

3 : Vector Initialization

    vector<int> fst(26,n), lst(26,0);

Declares two vectors `fst` and `lst` to store the first and last occurrence indices of each character in the string `num`.

4 : For Loop Start

    for(int i = 0; i < n; i++) {

Starts a loop that iterates through each character in the string `num`.

5 : First Occurrence Update

        fst[num[i]-'a']= min(fst[num[i]-'a'], i);

Updates the first occurrence of the character `num[i]` in the `fst` vector, ensuring it holds the smallest index.

6 : Last Occurrence Update

        lst[num[i]-'a'] = i;

Updates the last occurrence of the character `num[i]` in the `lst` vector with the current index.

7 : Second For Loop Start

    for(int i = 0; i < 26; i++) {

Starts a second loop that iterates over all possible characters (from 'a' to 'z').

8 : Palindrome Count Calculation

if(fst[i] < lst[i]) res += unordered_set<char>(num.begin() + fst[i] + 1, num.begin() + lst[i]).size();

For each character, if it appears more than once, calculates the number of distinct characters between its first and last occurrences, adding this count to `res`.

9 : Return Statement

    return res;

Returns the total count of distinct palindromic subsequences.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) because we iterate over the string once to compute the first and last occurrences.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) because we only use constant space to store the first and last occurrences of characters.

Leetcode 1930: Unique Length-3 Palindromic Subsequences

Explore →