Given a valid compressed string compressed made of pairs, each consisting of a lowercase English letter followed by its positive frequency. Return a compressed string in which each distinct letter appears exactly once with its total frequency, in alphabetical order.
Example 1
Input: compressed = "d5e2d2a4d8b12a7"
Output: "a11b12d15e2"
Explanation: The two a pairs contribute 4 + 7 = 11, and the three d pairs contribute 5 + 2 + 8 = 15. The totals for b and e are 12 and 2. The
Example 2
Input: compressed = "d4a3c2a2c5"
Output: "a5c7d4"
Explanation: The two counts for a add up to 5, and the two counts for c add up to 7. The count for d is 4. The result lists them in the order a, c, d.
Approach
A pair's frequency gives its entire contribution to the letter's total. A frequency map stores one total per letter, so separate pairs for the same letter all contribute to the same entry.
Each map entry holds the sum of that letter's frequencies in the pairs read so far. Once all pairs have been read, sorting the distinct keys gives the required alphabetical order. Each key contributes one letter and its final total to the result.
Algorithm
Start with an empty frequency map and read the first letter.
Start the frequency for each new pair at zero. For every following digit, multiply the partial frequency by ten and add the digit's numeric value. Continue building this one frequency until the next letter is encountered or the string ends.
Add the parsed frequency to that letter's total in the map. Use zero as the previous total for a letter seen for the first time.
Repeat until the input ends, then collect and sort the distinct keys. An input with one pair gives a single key.
Append each sorted key and its total frequency to the result.
Return the assembled string.
Dry Run
Better Compression of String
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the compression with one total per letter in alphabetical order. string betterCompression(const string& compressed) { unordered_map<char, int> freqMap; int index = 0; int length = compressed.size(); // Read each letter and its full frequency. while (index < length) { char letter = compressed[index++]; int frequency = 0; // Consume the digits that belong to this letter. while (index < length && isdigit(compressed[index])) { frequency = frequency * 10 + (compressed[index] - '0'); index++; } // A new map entry starts at zero before this count is added. freqMap[letter] += frequency; } vector<char> letters; // Collect one key for each distinct letter in the map. for (const auto& entry : freqMap) { letters.push_back(entry.first); } sort(letters.begin(), letters.end()); string result; // Append the letters in alphabetical order with their final totals. for (char letter : letters) { result += letter; result += to_string(freqMap[letter]); } return result; }};// Driver codeint main() { string compressed = "d5e2d2a4d8b12a7"; // instance for class Solution Solution sol; cout << "Output: " << sol.betterCompression(compressed) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N + K log K) expected time because parsing and hash-map updates take O(N) expected time, and sorting the K keys takes O(K log K) time.
Space Complexity: O(K) auxiliary space for the map and sorted keys, with a bounded number of digits per total.
Interview follow-up Questions
The frequency includes every digit after the current letter up to the next letter or the end of the string. For b120a4, the digits 1, 2, and 0 build the count 120. The a starts the next pair.
Be the first to add a comment.