1930. Unique Length-3 Palindromic Subsequences

String Hash Table

Intuition

A length-3 palindromic string p has the property that p[0] == p[2], regardless of the middle character p[1].

Approach

Iterate through the given string s, and store the first and last index of each unique character in a hash map, pos, where they key is a character, and the value is an array of two integers representing the first and last indices of that character in s.
For each character c in the hash map, the number of valid palindromic subsequence of the form cXc corresponds to the number of unique characters X that occur between the first and last occurrence of c (i.e., within the range [pos[c][0], pos[c][1])).

Code

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        pos = {}
        for i, c in enumerate(s):
            if c not in pos:
                pos[c] = [i, i]
            else:
                pos[c][1] = i

        res = 0
        for c, idx in pos.items():
            res += len(set(s[idx[0] + 1 : idx[1]]))
        return res

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int first[26] = {}, last[26] = {}, res = 0;
        fill(begin(first), end(first), -1);
        for (int i = 0; i < s.size(); i++) {
            if (first[s[i] - 'a'] == -1) {
                first[s[i] - 'a'] = i;
            }
            last[s[i] - 'a'] = i;
        }
        for (int i = 0; i < 26; i++) {
            if (first[i] < last[i] - 1) {
                res += unordered_set<char>(begin(s) + first[i] + 1,
                                           begin(s) + last[i])
                           .size();
            }
        }
        return res;
    }
};

class Solution {
    public int countPalindromicSubsequence(String s) {
        Map<Character, int[]> pos = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (!pos.containsKey(c)) {
                pos.put(c, new int[] { i, i });
            } else {
                int[] val = pos.get(c);
                val[1] = i;
            }
        }

        int res = 0;
        for (Map.Entry<Character, int[]> entry : pos.entrySet()) {
            int[] val = entry.getValue();
            Set<Character> occur = new HashSet<>();
            for (int i = val[0] + 1; i < val[1]; i++) {
                occur.add(s.charAt(i));
            }
            res += occur.size();
        }

        return res;
    }
}

Complexity

Time complexity: $O(N)$
Space complexity: $O(1)$