Given a string, find and print the frequency of every character in sorted order that appears in it. For each unique character, output the character along with how many times it occurs.
Example 1
Input: s = "hello"
Output: e1 h1 l2 o1
Explanation: Characters in sorted order are e, h, l, and o. Character l appears for two times, and every other character appears only once.
Example 2
Input: s = "aabccc"
Output: a2 b1 c3
Explanation: Characters are already in sorted order. Character a appears two times, b appears one time, and c appears three times.
Brute Force Approach
The simplest way is to process each character one by one and count how many times it appears by scanning the entire string. To avoid counting the same character multiple times, skip any character that has already been processed earlier. After collecting the frequency of every distinct character, sort the results alphabetically before returning them.
Algorithm
If the string is empty, return an empty list.
An empty list is created to store the character-frequency pairs.
For each character in the string, count the frequency of the character traversing the entire array or skip it if already visited earlier.
All stored pairs are sorted by character and the list is returned.
Dry Run
Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns character frequencies using direct counting vector<pair<char, int>> characterFrequency(string s) { vector<pair<char, int>> answer; // Empty string has no character-frequency pair if (s.empty()) { return answer; } // Process every character position for (int i = 0; i < s.size(); i++) { bool alreadyCounted = false; // Check earlier positions to avoid duplicate counting for (int j = 0; j < i; j++) { // Same character was already counted before if (s[j] == s[i]) { alreadyCounted = true; break; } } // Skip characters already counted if (alreadyCounted) { continue; } int frequency = 0; // Count the current character in the full string for (int j = 0; j < s.size(); j++) { // Matching character increases the frequency if (s[j] == s[i]) { frequency++; } } answer.push_back({s[i], frequency}); } sort(answer.begin(), answer.end()); return answer; }};// Driver code starts// Runs a sample test for the brute force solutionint main() { string s = "hello"; Solution solution; vector<pair<char, int>> answer = solution.characterFrequency(s); // Print pairs as character followed by frequency for (int i = 0; i < answer.size(); i++) { // Add a space before every pair except the first if (i > 0) { cout << " "; } cout << answer[i].first << answer[i].second; } cout << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N² + Klog(K)) - where N is the length of the string and K is the number of unique characters. For each new character, the entire string is scanned, and the final list of K unique characters is sorted.
Space Complexity: O(K) - where K is the number of pairs stored in answer.
Better Approach
Instead of scanning the entire string for every new character, first sort the string so that identical characters become adjacent. Then, the sorted string can be traversed once and the size of each consecutive group is counted. Since the characters are already sorted, the output is produced in alphabetical order automatically.
Algorithm
If the string is empty, return an empty list.
The string is sorted and an empty list is created to store the pairs.
Start from the first character and count the length of each consecutive group of identical characters.
The current character and its frequency is stored in the list as one pair.
Continue the process and return the list of character-frequency pairs.
Dry Run
Better
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns character frequencies by sorting and grouping characters vector<pair<char, int>> characterFrequency(string s) { vector<pair<char, int>> answer; // Empty string has no character-frequency pair if (s.empty()) { return answer; } sort(s.begin(), s.end()); int start = 0; // Read one equal-character group at a time while (start < s.size()) { int end = start; // Move across the current character group while (end < s.size() && s[end] == s[start]) { end++; } answer.push_back({s[start], end - start}); start = end; } return answer; }};// Driver code starts// Runs a sample test for the sorting solutionint main() { string s = "hello"; Solution solution; vector<pair<char, int>> answer = solution.characterFrequency(s); // Print pairs as character followed by frequency for (int i = 0; i < answer.size(); i++) { // Add a space before every pair except the first if (i > 0) { cout << " "; } cout << answer[i].first << answer[i].second; } cout << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N log(N)), where N is the length of the string. Sorting the string is the expensive step, while the single pass through the sorted string takes O(N) time.
Space Complexity: O(K) - where K is the number of pairs stored in answer.
Optimal Approach 1
Sorting the string is not really necessary when the objective is only to count how many times each character appears. A frequency map can record the count of every character in a single traversal of the string. After counting all characters, simply read the unique characters in sorted order and record their frequencies.
Algorithm
If the string is empty, return an empty list.
A frequency map can be created to count the occurrences of every character.
Then the entire array is traversed and the frequency of each character is stored in the map.
All the character - frequency pairs are copied in a list in sorted fashion.
Return the list of character-frequency pairs.
Dry Run
Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns character frequencies using an ordered frequency map vector<pair<char, int>> characterFrequency(string s) { vector<pair<char, int>> answer; // Empty string has no character-frequency pair if (s.empty()) { return answer; } map<char, int> frequency; // Count every character in sorted-key storage for (char character : s) { frequency[character]++; } // Convert sorted map entries into the answer for (auto entry : frequency) { answer.push_back({entry.first, entry.second}); } return answer; }};// Driver code starts// Runs a sample test for the ordered map solutionint main() { string s = "hello"; Solution solution; vector<pair<char, int>> answer = solution.characterFrequency(s); // Print pairs as character followed by frequency for (int i = 0; i < answer.size(); i++) { // Add a space before every pair except the first if (i > 0) { cout << " "; } cout << answer[i].first << answer[i].second; } cout << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N + K log(K))where N is the length of the string and K is the number of distinct characters. The string is scanned once to count the frequency of each character, and the distinct characters are then arranged in sorted order.
Space Complexity: O(K), where K is the number of distinct characters used in the frequency map.
Optimal Approach 2
Since the string contains only lowercase English letters, a hash map is not required. A fixed-size array of 26 elements can directly store the frequency of each character. Each character is mapped to an index from 0 to 25, allowing the frequencies to be counted in a single traversal. Finally, the array is scanned from 'a' to 'z' to collect all characters that appear in the string.
Algorithm
If the string is empty, return an empty list.
Create a frequency array of size 26 and initialize all values to 0.
Then the string is traversed once and the count corresponding to each character is incremented.
Traverse the frequency array from index
0to25. For every index with a non-zero frequency, the corresponding character and its frequency can be added to the answer.Return the list of character-frequency pairs.
Dry Run
Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns character frequencies using a fixed-size frequency array vector<pair<char, int>> characterFrequency(string s) { vector<pair<char, int>> answer; // Empty string has no character-frequency pair if (s.empty()) { return answer; } vector<int> frequency(26, 0); // Count every character for (char character : s) { frequency[character - 'a']++; } // Store all characters with non-zero frequency for (int i = 0; i < 26; i++) { if (frequency[i] > 0) { answer.push_back({'a' + i, frequency[i]}); } } return answer; }};// Driver code starts// Runs a sample test for the frequency array solutionint main() { string s = "hello"; Solution solution; vector<pair<char, int>> answer = solution.characterFrequency(s); // Print pairs as character followed by frequency for (int i = 0; i < answer.size(); i++) { // Add a space before every pair except the first if (i > 0) { cout << " "; } cout << answer[i].first << answer[i].second; } cout << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N) – where N is the length of the string. The string is traversed once to count frequencies, and the frequency array of size 26 is scanned once.
Space Complexity: O(1) – only a fixed-size array of 26 elements is used, which does not depend on the length of the string.
Be the first to add a comment.