# Intuition\nTo create a 5 digit palindrome we do not need to care about the middle element. We just need to find subsequence of pattern XY_YX. Calculate number of subsequences of type XY and subsequences of type YX around any given point `i` and multiply them to find number of subsequences of type XY_YX. Since string only has digits, the time complexity will be 100*n.\n\n# Approach\n* We will be maintaing the counts of digit in the list `cnts`\n* Keep 2 arrays pre and suf to store the number of prefixes of type XY and suffixes of type YX. `pre[i-1][1][2]` means prefixes of type `12` before index i. Similarly `suf[i+1][1][2]` means suffixes of type `21` after index i\n* Remember given string is made of digits that is `0123456789`. That\'s a total of 10 unique characters\n* Once we have calculated the prefix and suffix lists we just need to multiply `pre[i - 1][j][k]` with `suf[i + 1][j][k]` to find number of palindromic subsequences\n```\n for (int i = 0; i < n; i++) {\n int c = s[i] - \'0\';\n if (i) {\n for (int j = 0; j < 10; j++)\n for (int k = 0; k < 10; k++) {\n pre[i][j][k] = pre[i - 1][j][k];\n if (k == c) pre[i][j][k] += cnts[j];\n }\n }\n cnts[c]++;\n }\n```\n* Explanation of above code:\n * Use `if (i)` to not step outside of array limits when accessing `pre[i-1]`\n * Let\'s say `j = 5`, `k = 4` and `c = 4` which means we are looking at prefix `54`. `pre[i][j][k] = pre[i - 1][j][k]` will carry forward previous count of prefixes. Since `k == c` means the current character(s[i]) matches with last digit of prefix. To find total number of possibilites of prefixes of type `54` we need to know how many `5` exist before current index. This information is stored in `cnts[5]`. So we add `cnts[5]` to `pre[i][5][4]`.\n \n![Screen Shot 2022-11-27 at 10.13.27 AM.png](https://assets.leetcode.com/users/images/aa300f55-d7b1-4f1f-a23f-d2d6fb7454a1_1669572828.8937273.png)\n\n\n\n# Complexity\n- Time complexity: O(n)\n\n- Space complexity: O(n)\n\n# Code\n\n**Python 3**\n```\ndef countPalindromes(self, s: str) -> int:\n mod, n, ans = 10 ** 9 + 7, len(s), 0\n pre, cnts = [[[0] * 10 for _ in range(10)] for _ in range(n)], [0] * 10\n for i in range(n):\n c = ord(s[i]) - ord(\'0\')\n if i:\n for j in range(10):\n for k in range(10):\n pre[i][j][k] = pre[i - 1][j][k] \n if k == c: pre[i][j][k] += cnts[j]\n cnts[c] += 1\n suf, cnts = [[[0] * 10 for _ in range(10)] for _ in range(n)], [0] * 10\n for i in range(n - 1, -1, -1):\n c = ord(s[i]) - ord(\'0\')\n if i < n - 1:\n for j in range(10):\n for k in range(10):\n suf[i][j][k] = suf[i + 1][j][k]\n if k == c: suf[i][j][k] += cnts[j]\n cnts[c] += 1\n for i in range(2, n - 2):\n for j in range(10):\n for k in range(10):\n ans += pre[i - 1][j][k] * suf[i + 1][j][k]\n return ans % mod\n```\n\n**C++**\n```\nint pre[10000][10][10], suf[10000][10][10], cnts[10] = {};\nint countPalindromes(string s) {\n int mod = 1e9 + 7, n = s.size(), ans = 0;\n for (int i = 0; i < n; i++) {\n int c = s[i] - \'0\';\n if (i)\n for (int j = 0; j < 10; j++)\n for (int k = 0; k < 10; k++) {\n pre[i][j][k] = pre[i - 1][j][k];\n if (k == c) pre[i][j][k] += cnts[j];\n }\n cnts[c]++;\n }\n memset(cnts, 0, sizeof(cnts));\n for (int i = n - 1; i >= 0; i--) {\n int c = s[i] - \'0\';\n if (i < n - 1)\n for (int j = 0; j < 10; j++)\n for (int k = 0; k < 10; k++) {\n suf[i][j][k] = suf[i + 1][j][k];\n if (k == c) suf[i][j][k] += cnts[j];\n }\n cnts[c]++;\n }\n for (int i = 2; i < n - 2; i++)\n for (int j = 0; j < 10; j++)\n for (int k = 0; k < 10; k++)\n ans = (ans + 1LL * pre[i - 1][j][k] * suf[i + 1][j][k]) % mod;\n return ans;\n}\n```\n\n**Java**\n```\npublic int countPalindromes(String s) {\n int mod = 1000_000_007, n = s.length(), ans = 0, cnts[] = new int[10],\n pre[][][] = new int[n][10][10], suf[][][] = new int[n][10][10];\n for (int i = 0; i < n; i++) {\n int c = s.charAt(i) - \'0\';\n if (i > 0)\n for (int j = 0; j < 10; j++)\n for (int k = 0; k < 10; k++) {\n pre[i][j][k] = pre[i - 1][j][k];\n if (k == c) pre[i][j][k] += cnts[j];\n }\n cnts[c]++;\n }\n Arrays.fill(cnts, 0);\n for (int i = n - 1; i >= 0; i--) {\n int c = s.charAt(i) - \'0\';\n if (i < n - 1)\n for (int j = 0; j < 10; j++)\n for (int k = 0; k < 10; k++) {\n suf[i][j][k] = suf[i + 1][j][k];\n if (k == c) suf[i][j][k] += cnts[j];\n }\n cnts[c]++;\n }\n for (int i = 2; i < n - 2; i++)\n for (int j = 0; j < 10; j++)\n for (int k = 0; k < 10; k++)\n ans = (int)((ans + 1L * pre[i - 1][j][k] * suf[i + 1][j][k]) % mod);\n return ans;\n}\n```

Count Palindromic Subsequences

Problem Description

Problem Description

Answer Panel