1930: Unique-Length-3-Palindromic-Subsequences
Medium

table of contents

This question felt slightly confusing, since it always felt like there was a more optimised solution.

My algorithm is simply to just:

Although, this seems quite inefficient, I do not believe there is a way for you to avoid iterating through the same letters 26 times, as each letter has unique first and last indexes, meaning regardless of however we order it, we would still have to iterate through parts of s repeatedly, meaning this simple solution might simply be better (haha?).

code

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        vector<int> start(26, -1);
        vector<int> end(26);

        for (int i = 0; i < s.size(); ++i) {
            if (start[s[i]-'a'] == -1) {
                start[s[i]-'a'] = i;
            }
            end[s[i]-'a'] = i;
        }
        
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            vector<int> letters(26);
            int counter = 0;
            if (start[i] < end[i]) {
                for (int j = start[i]+1; j < end[i]; ++j) {
                    if (letters[s[j]-'a'] == 0) {
                        letters[s[j]-'a'] = 1;
                        ++counter;
                        if (counter == 26) {
                            break;
                        }
                    }
                }
            }
            ans += counter;
        }
        return ans;
    }
};

complexity