countPalindromicSubsequence(s): Input string s Output number of unique palindromic subsequences in s of length 3 visited = empty set ans = 0 for every character c in s: if c in set: continue end if add c to visited firstOccurrence = -1 lastOccurrence = -1 for every i from 0 to s.length(): if firstOccurrence == -1: firstOccurrence = i // Ensure that firstOccurrence only updates once end if lastOccurrence = i end for unique = empty set for every i from firstOccurrence + 1 to lastOccurrence: add s[i] to unique end for ans += unique.size() end for return ans

Complexity

Time complexity: $O(n)$.

At most $\Sigma = 26$ iterations of outer loop.

In each iteration:

Find firstOccurrence and lastOccurence is $O(n)$.

Create unique set is $O(n)$.

Overall complexity is $O(\Sigma n) = O(n)$.

Space complexity: $O(\Sigma)$.

s only contains lowercase English letters, so $\Sigma = 26$.

As a consequence, the maximum size of visited and unique is 26.

classSolution { public: intcountPalindromicSubsequence(string s){ int ans = 0; unordered_set<char> visited; for (char c : s) { if (visited.find(c) != visited.end()) { continue; } visited.insert(c); // Find the first and last occurence of c int lastOccurrence = -1; int firstOccurrence = -1; for (int j = 0; j < s.length(); j++) { if (s[j] == c) { if (firstOccurrence == -1) { // firstOccurence can only be updated once firstOccurrence = j; } lastOccurrence = j; } } // Count the number of unique characters between i and lastOccurance unordered_set<char> unique; for (int j = firstOccurrence+1; j < lastOccurrence; j++) { unique.insert(s[j]); } ans += unique.size(); } return ans; } };