leetcode

commit 1c894d773dd8205cb7ed12e88117d935b7cdb6ea
parent 5a19b6d0e4927c1462e5beffeb6820ecbf4eeaf7
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed,  7 Feb 2024 17:15:11 +0000

Improved Daily Problem

Diffstat:
M
Problems/0451.cpp
 | 
39
+++++++++++++++++++++++++++++++++------

1 file changed, 33 insertions(+), 6 deletions(-)
diff --git a/Problems/0451.cpp b/Problems/0451.cpp
@@ -1,11 +1,38 @@
 class Solution {
   public:
-    string frequencySort(string s) {
-        array<int, 128> um = {0};
+    string frequencySort(string &s) const {
+        unordered_map<char, int> freq;
+        vector<string> bucket(size(s) + 1);
+
         for (char c : s)
-            um[c]++;
-        sort(s.begin(), s.end(),
-             [&um](char a, char b) { return um[a] > um[b] || (um[a] == um[b] && a < b); });
-        return s;
+            freq[c]++;
+        for (auto [c, n] : freq)
+            bucket[n].append(n, c);
+
+        string res;
+        for (int i = s.size(); i > 0; i--) {
+            if (!bucket[i].empty()) res.append(bucket[i]);
+        }
+
+        return res;
+    }
+};
+
+class Solution {
+  public:
+    string frequencySort(const string &s) const {
+        static pair<int, char> count[128];
+
+        for (int i = 0; i < size(count); i++)
+            count[i] = {0, i};
+        for (const char c : s)
+            count[c].first++;
+        sort(rbegin(count), rend(count));
+
+        string res;
+        for (const auto [n, c] : count)
+            res += string(n, c);
+
+        return res;
     }
 };