Unique Length-3 Palindromic Subsequences

class Solution {
public:
    int countPalindromicSubsequences(string str) {
        vector<int> startPos(26, -1);
        vector<int> endPos(26, -1);
            
        for (int pos = 0; pos < str.length(); pos++) {
            int index = str[pos] - 'a';
            if (startPos[index] == -1) {
                startPos[index] = pos;
            }
                
            endPos[index] = pos;
        }
            
        int total = 0;
        for (int i = 0; i < 26; i++) {
            if (startPos[i] != -1 && startPos[i] != endPos[i]) {
                unordered_set<char> uniqueChars;
                for (int j = startPos[i]+1; j < endPos[i]; j++) {
                    uniqueChars.insert(str[j]);
                }
                    
                total += uniqueChars.size();
            }
        }
            
        return total;
    }
};

This solution aims to count unique length-3 palindromic subsequences in a given string using C++. A palindromic subsequence of length 3 has the form ABCBA, where A and B are the same characters.

Here's a concise explanation of the provided approach:

1. Initialize two vectors, startPos and endPos, of size 26 (for each letter of the alphabet) to track the start and end positions of each character in the string.
2. Iterate through the string to update startPos with the first occurrence and endPos with the last occurrence of each character.
3. Set a counter, total, to accumulate the number of unique palindromic subsequences.
4. Iterate through the alphabet (0 to 25 representing 'a' to 'z'). For each character that appears more than once in the string (i.e., has different start and end positions), use a set, uniqueChars, to collect unique characters that reside between the first and the last occurrence of the current character.
5. Add the size of uniqueChars to the total for each set of characters, which represents the count of unique length-3 palindromic subsequences that can be formed with the current character as the first and last character.

This method efficiently harnesses the properties of palindromes and sets to avoid counting duplicates, ensuring an accurate total of palindromic subsequences. The use of unordered sets helps in achieving an average constant time complexity for operations like insertions and look-ups, hence optimizing the process.

class Solution {
    public int countUniquePalindromicSubsequences(String str) {
        int[] startPos = new int[26];
        int[] endPos = new int[26];
        Arrays.fill(startPos, -1);
            
        for (int idx = 0; idx < str.length(); idx++) {
            int charIndex = str.charAt(idx) - 'a';
            if (startPos[charIndex] == -1) {
                startPos[charIndex] = idx;
            }
                
            endPos[charIndex] = idx;
        }
            
        int result = 0;
        for (int i = 0; i < 26; i++) {
            if (startPos[i] == -1) continue;
                
            Set<Character> uniqueChars = new HashSet<>();
            for (int j = startPos[i] + 1; j < endPos[i]; j++) {
                uniqueChars.add(str.charAt(j));
            }
                
            result += uniqueChars.size();
        }
            
        return result;
    }
}

In the Java solution presented, the goal is to find the number of unique length-3 palindromic subsequences in a given string. The implementation effectively employs two integer arrays, startPos and endPos, to track the starting and ending positions of each character (from 'a' to 'z') in the string, initializing all positions to -1 initially. For each character in the string, you calculate the character's index in the alphabet, and if the character appears for the first time, you set startPos at this index to the current position. In contrast, endPos is updated for each character occurrence to mark the most recent position.

With the positions recorded, the solution iterates over the potential 26 letters (from 'a' to 'z'). For each character that appears in the string (startPos[i] is not -1), the code constructs a set of characters (uniqueChars) found between the first and last occurrences of this character (exclusive). The use of a HashSet filters out any duplicates, ensuring only unique characters are counted.

For each such character with valid start and end positions, the size of uniqueChars (number of unique characters between the first and last occurrences of the current character) is added to result. This summand reflects the number of unique length-3 subsequences for which the current character is the first and last character, and the characters in uniqueChars serve as the middle character.

The function eventually returns result, which is the total count of unique palindromic subsequences of length 3 found in the input string.

This approach is efficient due to its direct use of basic data structures (arrays and sets) and the linear scan through the string, combined with specific character position management, resulting in a robust solution to the problem without unnecessary complexity.

class Solution:
    def countUniquePalindromes(self, string: str) -> int:
        start_position = [-1] * 26
        end_position = [-1] * 26
    
        for index in range(len(string)):
            position = ord(string[index]) - ord("a")
            if start_position[position] == -1:
                start_position[position] = index
    
            end_position[position] = index
    
        count = 0
        for char_index in range(26):
            if start_position[char_index] == -1:
                continue
                
            unique_chars = set()
            for j in range(start_position[char_index] + 1, end_position[char_index]):
                unique_chars.add(string[j])
                
            count += len(unique_chars)
    
        return count

This Python code defines a method countUniquePalindromes that determines the number of unique palindromic subsequences of length 3 in a given string. The approach involves tracking the first and last positions of each character in the alphabet within the string, and then counts the distinct characters between these positions for potential palindromes.

Here are the key operations performed in the code:

• Initializes two lists, start_position and end_position, each of size 26 to accommodate all lowercase alphabet letters, setting initial values to -1. These lists will hold the first and last occurrence indexes of each character respectively.
• Iterates over the string to update start_position and end_position based on the first and last occurrence of each character.
• Uses a loop to go through each character (from 'a' to 'z'). For characters found in the string, it records all unique characters lying between the first and last occurrences of this character.
• The set unique_chars is used to store these unique characters. The length of this set (representing distinct characters) indicates potential unique palindromic subsequences for that focal character.
• Accumulates the count of these unique middle characters for all valid characters in the string.

Finally, the method returns the total count of unique palindromic subsequences of length 3, derived from the distinct middle characters lying between each pair of identical characters marking the subsequences’ boundaries.