Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 14

Description

Unique Length-3 Palindromic Subsequences

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")

Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")

Constraints:

• 3 <= s.length <= 105
• s consists of only lowercase English letters.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  int countPalindromicSubsequence(string s) {
    vector<int> front(128, -1);
    vector<int> back(128, -1);
    for(int i = 0; i < s.length(); ++i) {
      if(front[s[i]] == -1) {
        front[s[i]] = i;
      }
      back[s[i]] = i;
    }
    int answer = 0;
    for(auto c = 'a'; c <= 'z'; ++c) {
      if(back[c] == front[c]) continue;
      set<char> st;
      for(int i = front[c] + 1; i < back[c]; ++i) {
        st.insert(s[i]);
      }
      answer += st.size();
    }

    return answer;
  }
};

// Accepted
// 70/70 cases passed (634 ms)
// Your runtime beats 33.56 % of cpp submissions
// Your memory usage beats 43.61 % of cpp submissions (13.8 MB)