leetcode

commit 226177df321c7e565875051333a4322b49ddf5b6
parent a1f043c44f6e2870178ff62025f2c3dce5a09932
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 14 Nov 2023 21:30:43 +0000

Daily Problem

Diffstat:
A
Problems/1930.cpp
 | 
61
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 62 insertions(+), 0 deletions(-)
diff --git a/Problems/1930.cpp b/Problems/1930.cpp
@@ -0,0 +1,61 @@
+class Solution {
+  public:
+    int countPalindromicSubsequence(const string &s) const {
+        static pair<int, int> pos[27];
+        memset(pos, 0xFF, sizeof(pos));
+
+        const int n = s.size();
+        for (int i = 0; i < n; i++) {
+            const int idx = s[i] & 0x1F;
+            if (pos[idx].first == -1) pos[idx].first = i;
+            pos[idx].second = i;
+        }
+
+        int res = 0;
+        for (int i = 1; i <= 26; i++) {
+            const auto [first, last] = pos[i];
+            if (first == -1) continue;
+            bitset<27> bs;
+            for (int j = first + 1; j < last; j++)
+                bs.set(s[j] & 0x1F);
+            res += bs.count();
+        }
+        return res;
+    }
+};
+
+// Improve constant factor by using a lot of memory
+class Solution {
+  public:
+    int countPalindromicSubsequence(const string &s) const {
+        static int count[100001][27];
+        memset(count, 0x00, sizeof(int) * 27);
+
+        static pair<int, int> pos[27];
+        memset(pos, 0xFF, sizeof(pos));
+
+        const int n = s.size();
+        for (int i = 0; i < n; i++) {
+            const int idx = s[i] & 0x1F;
+            if (i != 0) memcpy(count[i], count[i - 1], sizeof(int) * 27);
+            count[i][idx]++;
+
+            if (pos[idx].first == -1) pos[idx].first = i;
+            pos[idx].second = i;
+        }
+
+        int res = 0;
+        for (int i = 1; i <= 26; i++) {
+            const auto [first, last] = pos[i];
+            if (first == -1) continue;
+
+            count[last][i]--;
+            for (int j = 1; j <= 26; j++) {
+                res += count[last][j] > count[first][j];
+            }
+            count[last][i]++;
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -755,6 +755,7 @@ for solving problems.
 |  1910  |   Medium   | [Remove All Occurrences of a Substring](Problems/1910.cpp)                                         |
 |  1921  |   Medium   | [Eliminate Maximum Number of Monsters](Problems/1921.cpp)                                          |
 |  1926  |   Medium   | [Nearest Exit from Entrance in Maze](Problems/1926.cpp)                                            |
+|  1930  |   Medium   | [Unique Length-3 Palindromic Subsequences](Problems/1930.cpp)                                      |
 |  1947  |   Medium   | [Maximum Compatibility Score Sum](Problems/1947.cpp)                                               |
 |  1962  |   Medium   | [Remove Stones to Minimize the Total](Problems/1962.cpp)                                           |
 |  1963  |   Medium   | [Minimum Number of Swaps to Make the String Balanced](Problems/1963.cpp)                           |