1
class Solution {
2
  public int countPalindromicSubsequence(String s) {
3

4
    int n = s.length();
5

6
    char[] chArr = s.toCharArray();
7

8
    int[] firstOcc = new int[26];
9
    int[] lastOcc = new int[26];
10

11
    Arrays.fill(firstOcc, -1);
12
    Arrays.fill(lastOcc, -1);
13

14
    for (int i = 0; i < n; i++) {
15

16
      char ch = chArr[i];
17

18
      if (firstOcc[ch - 'a'] == -1) {
19
        firstOcc[ch - 'a'] = i;
20
      }
21

22
      lastOcc[ch - 'a'] = i;
23
    }
24

25
    int ans = 0, count = 0;
26

27
    boolean[] visited;
28

29
    // check for each character ( start or end of palindrome )
30
    for (int i = 0; i < 26; i++) {
31

32
      int si = firstOcc[i]; // si - starting index
33
      int ei = lastOcc[i]; // ei - ending index
34

35
      visited = new boolean[26];
36

37
      count = 0;
38

39
      // check for unique charcters ( middle of palindrome )
40
      for (int j = si + 1; j < ei; j++) {
41

42
        if (!visited[chArr[j] - 'a']) {
43
          visited[chArr[j] - 'a'] = true;
44
          count++;
45
        }
46
      }
47

48
      ans += count;
49
    }
50

51
    return ans;
52
  }
53
}