leetcode

commit 9ec6d024c55822ec5aba1bf027e85d23b33a56a0
parent ac0a339571cb3b7fa386b1b519989c61952b87e9
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 24 May 2024 11:54:30 +0200

Daily Problem

Diffstat:
A
Problems/1255.cpp
 | 
50
++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 51 insertions(+), 0 deletions(-)
diff --git a/Problems/1255.cpp b/Problems/1255.cpp
@@ -0,0 +1,50 @@
+class Solution {
+    static int count[16][27];
+    mutable array<int, 26> crnt{0};
+
+    int rec(const int n, const int idx = 0, const int score = 0) const {
+        if (idx == n) return score;
+
+        int res = rec(n, idx + 1, score);
+        auto back = crnt;
+        for (int i = idx; i < n; i++) {
+            bool valid = true;
+            for (int j = 0; j < 26; j++) {
+                crnt[j] += count[i][j];
+                if (crnt[j] > count[n][j]) {
+                    valid = false;
+                    break;
+                }
+            }
+            if (valid) res = max(res, rec(n, i + 1, score + count[i][26]));
+            crnt = back;
+        }
+
+        return res;
+    }
+
+  public:
+    int maxScoreWords(const vector<string> &words, const vector<char> &letters,
+                      const vector<int> &score) const {
+        memset(count, 0x00, sizeof(count));
+
+        const int n = size(words);
+        for (int i = 0; i < n; i++) {
+            for (const char c : words[i]) {
+                const int idx = c - 'a';
+                count[i][26] += score[idx];
+                count[i][idx]++;
+            }
+        }
+
+        for (const char c : letters) {
+            const int idx = c - 'a';
+            count[n][26] += score[idx];
+            count[n][idx]++;
+        }
+
+        return rec(n);
+    }
+};
+
+int Solution::count[16][27];
diff --git a/README.md b/README.md
@@ -705,6 +705,7 @@ for solving problems.
 |  1249  |   Medium   | [Minimum Remove to Make Valid Parentheses](Problems/1249.cpp)                                      |
 |  1251  |    Easy    | [Average Selling Price](Problems/1251.cpp)                                                         |
 |  1254  |   Medium   | [Number of Closed Islands](Problems/1254.cpp)                                                      |
+|  1255  |    Hard    | [Maximum Score Words Formed by Letters](Problems/1255.cpp)                                         |
 |  1261  |   Medium   | [Find Elements in a Contaminated Binary Tree](Problems/1261.cpp)                                   |
 |  1266  |    Easy    | [Minimum Time Visiting All Points](Problems/1266.cpp)                                              |
 |  1267  |   Medium   | [Count Servers that Communicate](Problems/1267.cpp)                                                |