Count the Frequency of Each Character
Solve this ProblemEasy15 min
Topics
BasicsStringsHashing
Companies
TCSInfosysWipro
Given a string
text, return how often each character occurs, as entries like "l:3", listed in the order the characters first appear. Spaces are not counted, and upper- and lowercase letters count separately.
This is frequency counting applied to characters. Rescanning the text for every new character works but costs O(n²); counting everything in one pass into a map is O(n). The extra requirement — report in first-appearance orderInsertion OrderThe order in which keys were first added to a map. Some maps remember it; others do not. — matters when choosing the map type.
Test Case 1:
Input:text = "hello world"
Output:["h:1", "e:1", "l:3", "o:2", "w:1", "r:1", "d:1"]
Explanation:Characters are listed in the order they first appear; spaces are skipped.
Test Case 2:
Input:text = "aaa"
Output:["a:3"]
Explanation:One distinct character.
Constraints
- ◆
1 ≤ text.length ≤ 1000 - ◆
text contains printable ASCII characters and at least one non-space character
Try the Dry Run
Approach & Solutions
Recount Each New CharacterBrute
Walk through the text. When a character appears for the first time (no earlier copy) and is not a space, count how many times it occurs in the whole text and record "char:count". Characters seen before are skipped, so each one is reported once — but every report rescans the entire text.
Time
O(n²)Space
O(k) for the outputJava
class Solution {
public String[] charFrequency(String text) {
List<String> result = new ArrayList<>();
for (int i = 0; i < text.length(); i++) {
char ch = text.charAt(i);
if (ch == ' ' || text.indexOf(ch) < i) {
continue;
}
int count = 0;
for (int j = 0; j < text.length(); j++) {
if (text.charAt(j) == ch) {
count++;
}
}
result.add(ch + ":" + count);
}
return result.toArray(new String[0]);
}
}One Counting Pass, Then Report in OrderOptimal
Count every non-space character in one pass, using a map that remembers insertion order (LinkedHashMap in Java, dict in Python, Map in JavaScript). C and C++ use a 128-slot count array plus a list of characters in the order they first appeared. Then report each character with its count in that order.
Time
O(n)Space
O(k)Java
class Solution {
public String[] charFrequency(String text) {
Map<Character, Integer> counts = new LinkedHashMap<>();
for (char ch : text.toCharArray()) {
if (ch != ' ') {
counts.merge(ch, 1, Integer::sum);
}
}
List<String> result = new ArrayList<>();
for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
result.add(entry.getKey() + ":" + entry.getValue());
}
return result.toArray(new String[0]);
}
}