Unique Length-3 Palindromic Subsequences solution and explanation

def countUniquePalindromes(s):
    n = len(s)
    result = set()
    after = [{} for _ in range(n)]
    before = [{} for _ in range(n)]

    for i in range(n - 2, -1, -1):
        after[i] = after[i + 1].copy()
        after[i][s[i + 1]] = after[i].get(s[i + 1], 0) + 1

    for i in range(1, n - 1):
        c = s[i]
        before[i] = before[i - 1].copy()
        before[i][s[i - 1]] = before[i].get(s[i - 1], 0) + 1

        for ch in before[i]:
            if ch in after[i]:
                result.add((ch, c, ch))

    return len(result)

# Example Usage
s = "aabca"
print(countUniquePalindromes(s))  # Output: 3

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define ALPHABET_SIZE 26

bool containsChar(char *set, char ch) {
    return set[ch - 'a'];
}

void addToSet(char *set, char ch) {
    set[ch - 'a'] = true;
}

int countUniquePalindromes(const char *s) {
    int n = strlen(s);
    int result = 0;
    bool before[ALPHABET_SIZE] = {0};
    bool after[ALPHABET_SIZE] = {0};
    bool found[ALPHABET_SIZE][ALPHABET_SIZE] = {0};

    for (int i = 0; i < n; i++)
        addToSet(after, s[i]);

    for (int i = 0; i < n; i++) {
        after[s[i] - 'a'] = false;
        for (int b = 0; b < ALPHABET_SIZE; b++) {
            if (containsChar(before, b + 'a') && containsChar(after, b + 'a')) {
                if (!found[s[i] - 'a'][b]) {
                    found[s[i] - 'a'][b] = true;
                    result++;
                }
            }
        }
        addToSet(before, s[i]);
    }
    return result;
}

int main() {
    char s[] = "aabca";
    printf("%d\n", countUniquePalindromes(s));
    return 0;
}

import java.util.HashSet;
import java.util.Set;

public class PalindromeSubsequences {
    public static int countUniquePalindromes(String s) {
        int n = s.length();
        Set<String> uniquePalindromes = new HashSet<>();

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    for (int k = i + 1; k < j; k++) {
                        uniquePalindromes.add("" + s.charAt(i) + s.charAt(k) + s.charAt(j));
                    }
                }
            }
        }

        return uniquePalindromes.size();
    }

    public static void main(String[] args) {
        String s = "aabca";
        System.out.println(countUniquePalindromes(s)); // Output: 3
    }
}

function countUniquePalindromes(s) {
    const n = s.length;
    const uniquePalindromes = new Set();
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (s[i] === s[j]) {
                for (let k = i + 1; k < j; k++) {
                    uniquePalindromes.add(`${s[i]}${s[k]}${s[j]}`);
                }
            }
        }
    }
    return uniquePalindromes.size;
}

// Example Usage
console.log(countUniquePalindromes('aabca'));  // Output: 3

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int ans = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            int l = s.find_first_of(c), r = s.find_last_of(c);
            int mask = 0;
            for (int i = l + 1; i < r; ++i) {
                int j = s[i] - 'a';
                if (mask >> j & 1 ^ 1) {
                    mask |= 1 << j;
                    ++ans;
                }
            }
        }
        return ans;
    }
};

function countPalindromicSubsequence(s: string): number {
    let ans = 0;
    const a = 'a'.charCodeAt(0);
    for (let ch = 0; ch < 26; ++ch) {
        const c = String.fromCharCode(ch + a);
        const l = s.indexOf(c);
        const r = s.lastIndexOf(c);
        let mask = 0;
        for (let i = l + 1; i < r; ++i) {
            const j = s.charCodeAt(i) - a;
            if (((mask >> j) & 1) ^ 1) {
                mask |= 1 << j;
                ++ans;
            }
        }
    }
    return ans;
}

public class Solution {
    public int CountPalindromicSubsequence(string s) {
        int ans = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            int l = s.IndexOf(c), r = s.LastIndexOf(c);
            int mask = 0;
            for (int i = l + 1; i < r; ++i) {
                int j = s[i] - 'a';
                if ((mask >> j & 1) == 0) {
                    mask |= 1 << j;
                    ++ans;
                }
            }
        }
        return ans;
    }
}

func countPalindromicSubsequence(s string) (ans int) {
	for c := 'a'; c <= 'z'; c++ {
		l, r := strings.Index(s, string(c)), strings.LastIndex(s, string(c))
		mask := 0
		for i := l + 1; i < r; i++ {
			j := int(s[i] - 'a')
			if mask>>j&1 == 0 {
				mask |= 1 << j
				ans++
			}
		}
	}
	return
}

impl Solution {
    pub fn count_palindromic_subsequence(s: String) -> i32 {
        let s_bytes = s.as_bytes();
        let mut ans = 0;
        for c in b'a'..=b'z' {
            if let (Some(l), Some(r)) = (
                s_bytes.iter().position(|&ch| ch == c),
                s_bytes.iter().rposition(|&ch| ch == c),
            ) {
                let mut mask = 0u32;
                for i in (l + 1)..r {
                    let j = (s_bytes[i] - b'a') as u32;
                    if (mask >> j & 1) == 0 {
                        mask |= 1 << j;
                        ans += 1;
                    }
                }
            }
        }
        ans
    }
}