Unique Length 3 Palindromic Subsequences

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

My algorithm is simply to just:

• iterate through and find the first and last index of each letter of the alphabet
• then, for each letter of the alphabet, if there exists more than 2 elements, iterate through all the letters between the first and last index and track all the unique letters

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

• Time: O(n)
• Space: O(1)