leetcode

commit b63855cf7ac47e69cc0454549065d2c5cbb4f430
parent a0d50931c2456237b75f86e5d2f4a0fe8f780025
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri,  1 Nov 2024 15:10:25 +0100

Daily Problem, 1 Random

Diffstat:
A
Problems/0336.cpp
 | 
66
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
Problems/1957.cpp
 | 
18
++++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 86 insertions(+), 0 deletions(-)
diff --git a/Problems/0336.cpp b/Problems/0336.cpp
@@ -0,0 +1,66 @@
+static bool isPalindrome(const string &s, int i, int j) {
+    while (i < j) {
+        if (s[i++] != s[j--]) return false;
+    }
+
+    return true;
+}
+
+class Trie {
+    struct Node {
+        Node *children[26] = {0};
+        vector<int> suffix;
+        int idx = -1;
+    } root;
+
+  public:
+    void insert(const string &s, int idx) {
+        Node *crnt = &root;
+
+        for (int i = size(s) - 1; i >= 0; i--) {
+            auto &child = crnt->children[s[i] - 'a'];
+            if (!child) child = new Node();
+            if (isPalindrome(s, 0, i)) crnt->suffix.push_back(idx);
+
+            crnt = child;
+        }
+
+        crnt->suffix.push_back(idx);
+        crnt->idx = idx;
+    }
+
+    void query(const string &s, int idx, vector<vector<int>> &res) const {
+        const Node *crnt = &root;
+        const int n = size(s);
+
+        for (int i = 0; i < n; i++) {
+            if (crnt->idx != -1 && crnt->idx != idx && isPalindrome(s, i, n - 1)) {
+                res.push_back({idx, crnt->idx});
+            }
+
+            crnt = crnt->children[s[i] - 'a'];
+            if (!crnt) return;
+        }
+
+        for (const auto n : crnt->suffix) {
+            if (n == idx) continue;
+            res.push_back({idx, n});
+        }
+    }
+};
+
+class Solution {
+  public:
+    vector<vector<int>> palindromePairs(const vector<string> &words) const {
+        const int n = size(words);
+        vector<vector<int>> res;
+        Trie trie;
+
+        for (int i = 0; i < n; i++)
+            trie.insert(words[i], i);
+        for (int i = 0; i < n; i++)
+            trie.query(words[i], i, res);
+
+        return res;
+    }
+};
diff --git a/Problems/1957.cpp b/Problems/1957.cpp
@@ -0,0 +1,18 @@
+class Solution {
+  public:
+    string makeFancyString(string &s) const {
+        char prev = '\0';
+        int i = 0, cnt = 0;
+
+        for (const char c : s) {
+            if (c == prev)
+                cnt++;
+            else
+                prev = c, cnt = 1;
+            if (cnt <= 2) s[i++] = c;
+        }
+
+        s.resize(i);
+        return s;
+    }
+};
diff --git a/README.md b/README.md
@@ -307,6 +307,7 @@ reference and a base for solving problems.
 |  0331  |   Medium   | [Verify Preorder Serialization of a Binary Tree](Problems/0331.cpp)                                |
 |  0332  |    Hard    | [Reconstruct Itinerary](Problems/0332.cpp)                                                         |
 |  0334  |   Medium   | [Increasing Triplet Subsequence](Problems/0334.cpp)                                                |
+|  0336  |    Hard    | [Palindrome Pairs](Problems/0336.cpp)                                                              |
 |  0337  |   Medium   | [House Robber III](Problems/0337.cpp)                                                              |
 |  0338  |    Easy    | [Counting Bits](Problems/0338.cpp)                                                                 |
 |  0341  |   Medium   | [Flatten Nested List Iterator](Problems/0341.cpp)                                                  |
@@ -1105,6 +1106,7 @@ reference and a base for solving problems.
 |  1945  |    Easy    | [Sum of Digits of String After Convert](Problems/1945.cpp)                                         |
 |  1947  |   Medium   | [Maximum Compatibility Score Sum](Problems/1947.cpp)                                               |
 |  1954  |   Medium   | [Minimum Garden Perimeter to Collect Enough Apples](Problems/1954.cpp)                             |
+|  1957  |    Easy    | [Delete Characters to Make Fancy String](Problems/1957.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)                           |
 |  1964  |    Hard    | [Find the Longest Valid Obstacle Course at Each Position](Problems/1964.cpp)                       |