15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Count frequency of characters in a string with one left-to-right scan: read each character and add one to its count. Keep the counts in a hash map, or in an array when the alphabet is fixed, such as a to z. The scan takes O(n) time, and the table needs O(d) space for d distinct characters.
| Time with a hash map | O(n) expected, one lookup and one update per character |
|---|---|
| Worst case with a hash map | O(n^2) if every lookup collides |
| Space with a hash map | O(d), d distinct characters, d <= n |
| Fixed alphabet array | O(n + k) time and O(k) space for k permitted characters |
| Absent character | Count 0 |
| Case and spaces | 'a' and 'A' are different; a space counts as a character |
A string is a sequence of characters. Read a character at an index, starting at index 0 and ending at the last index.
A character’s frequency is the number of times it occurs.
For example, in "baba":
a occurs twice.b occurs twice.z occurs zero times.A frequency table associates each character with a nonnegative count. The table records how many times each character appears. It does not preserve the original character order.
Use a left-to-right scan: read one character, update one count, then move to the next index.
For array-based counting and symbol-table context, see the Algorithms, 4th edition companion site.
Use this input:
1text = "baba"
2count characters a and bWrite the string with its indices:
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Character | b | a | b | a |
Before reading any character, create counts for the tracked characters and set both to zero.
| Character | Count |
|---|---|
a | 0 |
b | 0 |
The scan index starts at i = 0.
1Processed prefix: ""
2Unprocessed suffix: "baba"The empty prefix contains no a and no b, so zero is the correct starting count for both characters.
Read exactly one character at each index. Increment only that character’s entry.
A frequency count updates exactly one entry per character read. Reading b, a, b, a gives counts a = 2 and b = 2; the table keeps counts, not the original order.
1i = 0
2counts = {a:0, b:0}
3processed prefix = ""No characters have been processed.
At i = 0, the character is b.
1text[0] = bIncrement the count for b.
1counts = {a:0, b:1}Now index 0 is processed.
1processed prefix = "b"
2next index = 1At i = 1, the character is a.
1text[1] = aIncrement the count for a.
1counts = {a:1, b:1}Now the processed prefix is "ba".
1next index = 2At i = 2, the character is b.
1text[2] = bIncrement the existing count for b.
1counts = {a:1, b:2}Now the processed prefix is "bab".
1next index = 3At i = 3, the character is a.
1text[3] = aIncrement the existing count for a.
1counts = {a:2, b:2}All four characters are now processed.
| Processed indices | Processed prefix | Counts |
|---|---|---|
| none | "" | {a:0, b:0} |
0 | "b" | {a:0, b:1} |
0..1 | "ba" | {a:1, b:1} |
0..2 | "bab" | {a:1, b:2} |
0..3 | "baba" | {a:2, b:2} |
After each update, the counts describe the characters already scanned.
More precisely, before processing index i:
After processing the prefix
text[0..i), each stored count equals the number of times its character occurs in that processed prefix, and the sum of stored frequencies isi.
Here, text[0..i) means the prefix beginning at index 0 and ending just before index i.
Check the statement against the example:
i = 0. The processed prefix is empty. The counts sum to 0.2, the processed prefix is "ba". The counts are {a:1, b:1}. Their sum is 2.{a:2, b:2}. Their sum is 4, the length of "baba".The statement is the loop invariant. It remains true throughout the scan.
The invariant records multiplicity only. It records no positions for a or b.
The invariant gives the required steps.
There are two count structures.
Suppose the task explicitly says that valid characters come from a fixed alphabet, such as lowercase a through z.
Use an array. Assign each permitted character an index. For lowercase letters, one possible mapping is:
1a -> 0, b -> 1, ..., z -> 25The array has one cell for every permitted character, including characters not encountered. Their counts remain zero.
For the example, if the fixed alphabet were a, b, c, the array-style representation could contain:
1a:2, b:2, c:0Use a character-to-count map. Add an entry when a character is encountered for the first time.
For "baba", the map eventually contains:
1a -> 2
2b -> 2Use a map when the task does not provide a bounded alphabet. A map also avoids deriving an array index for an unsupported character.
The following version uses a map because it accepts all encountered characters without requiring a fixed alphabet.
getOrDefault(counts, ch, defaultValue):
counts, a character ch, and a nonnegative integer defaultValue.counts[ch] if ch is a key in the map; otherwise defaultValue.counts.11 function characterFrequency(text)
22 input: text, a string of length n
33 return: a map from each encountered character to its frequency
44 mutation: does not modify text; creates and returns a new map
55
66 counts <- empty map
77
88 for i <- 0 to length(text) - 1
99 ch <- text[i]
1010 counts[ch] <- getOrDefault(counts, ch, 0) + 1
1111
1212 return countsThe loop boundary includes index 0 and ends at length(text) - 1. If text is empty, the loop executes zero times and the function returns an empty map.
11 function frequencyOf(text, ch)
22 input: text, a string; ch, one character
33 return: the frequency of ch in text, or 0 if ch is absent
44 mutation: does not modify text or ch
55
66 counts <- characterFrequency(text)
77 return getOrDefault(counts, ch, 0)For a fixed alphabet array, initialization must create all k count cells and set every cell to zero before the scan. Each scanned character must be validated as part of that alphabet before its array index is used.
Dry-run characterFrequency("baba") line by line.
| Executed line | i | ch | counts | Reason |
|---|---|---|---|---|
| 6 | — | — | {} | Create an empty map. |
| 8, first iteration | 0 | — | {} | The loop begins at index 0. |
| 9 | 0 | b | {} | Read text[0]. |
| 10 | 0 | b | {b:1} | b is absent, so use 0; store 0 + 1. |
| 8, second iteration | 1 | — | {b:1} | Move to index 1. |
| 9 | 1 | a | {b:1} | Read text[1]. |
| 10 | 1 | a | {b:1, a:1} | a is absent, so use 0; store 0 + 1. |
| 8, third iteration | 2 | — | {b:1, a:1} | Move to index 2. |
| 9 | 2 | b | {b:1, a:1} | Read text[2]. |
| 10 | 2 | b | {b:2, a:1} | Existing count is 1; store 1 + 1. |
| 8, fourth iteration | 3 | — | {b:2, a:1} | Move to index 3. |
| 9 | 3 | a | {b:2, a:1} | Read text[3]. |
| 10 | 3 | a | {b:2, a:2} | Existing count is 1; store 1 + 1. |
| 12 | — | — | {b:2, a:2} | Return the completed map. |
Dry-run the query for an absent character:
1frequencyOf("baba", 'z'){b:2, a:2}.z.z is not a key, so getOrDefault(counts, 'z', 0) returns 0.We prove that characterFrequency returns the correct frequency for every encountered character.
Before the loop starts, line 6 creates an empty map.
The processed prefix is text[0..0), which is empty. There are no stored character counts yet, so the sum of stored frequencies is 0. For any character that has not appeared, its effective count through getOrDefault is 0.
The invariant holds before the first iteration.
Assume the invariant is true before an iteration at index i.
The processed prefix is text[0..i). Line 9 reads exactly the next character, text[i]. Line 10 increments exactly the entry for that character.
text[i] increases by one, matching its one new occurrence in the larger prefix text[0..i+1).i to i + 1.The invariant holds for the next iteration.
The loop processes every index from 0 through length(text) - 1 exactly once.
When the loop ends, i = length(text). The processed prefix is the whole string. By the invariant, every stored count equals the number of times that character occurs in the full input.
characterFrequency returns correct counts for all encountered characters.
For frequencyOf, the function first obtains these correct counts. If ch is present, it returns that count. If ch is absent, getOrDefault returns 0, the correct frequency for a character with no occurrences.
The result does not reveal the original order of characters. Equal frequency tables can come from different character orders.
Let n be length(text).
The loop runs once for each input character.
During each iteration, it performs:
text[i];For a hash map, lookup and update are expected O(1). The expected scan time is:
1n iterations × O(1) work per iteration = O(n) timeIn the worst case, a map lookup or update can take O(d) when collisions require examining stored entries. Since d <= n, each iteration can take O(n) work:
1n iterations × O(n) work per iteration = O(n²) timeIf the map stores d distinct encountered characters, it has d entries.
1auxiliary space = O(d), where d <= nThe returned map is also the count result. Apart from that count structure, the loop uses only a constant number of variables: i and ch.
Let the explicitly bounded alphabet contain k permitted characters.
Before scanning, initialize all k array cells to zero. Then scan the n input characters and update one array cell per character.
1initialization work = O(k)
2scan work = O(n)
3total time = O(n + k)The count array contains k cells:
1auxiliary space = O(k)If k is treated as a fixed constant with respect to n, this is O(1) auxiliary space with respect to the string length.
Incorrect initialization:
1counts[ch] <- 1for every tracked character before scanning.
Smallest exposing input:
1text = "a"Wrong state:
1initial count(a) = 1
2after reading a, count(a) = 2Wrong output:
1count(a) = 2Correction: initialize every count to 0. The empty processed prefix contains zero occurrences of every tracked character.
Incorrect update:
1counts[ch] <- 1inside the scan loop.
Exposing input:
1text = "baba"Wrong final state:
1counts = {a:1, b:1}Each repeated occurrence overwrites the earlier count.
Correction:
1counts[ch] <- previous count for ch + 1For a map, obtain the previous count with a default of zero.
Incorrect assumption:
1'a' and 'A' represent the same characterwhen the task did not specify preprocessing.
Exposing input:
1text = "aA"Wrong output:
1count(a) = 2Correction: treat displayed characters as distinct unless the task explicitly requires normalization. With case significant:
1count(a) = 1
2count(A) = 1Incorrect approach: use a fixed lowercase-a-to-z array and derive an index for every input character without checking whether it belongs to that alphabet.
Exposing input:
1text = "A"Wrong result: an out-of-range index or a count placed in an incorrect cell.
Correction: validate that every input character is in the fixed alphabet, or use a map when the possible characters are not fixed.
If spaces are included in the string, they are characters too.
Concrete input:
1text = "a a"The correct frequencies include:
1count(a) = 2
2count(' ') = 1A fixed alphabet that excludes spaces cannot represent this input unless the task states that spaces should be removed first.
Implement these functions:
1characterFrequency(text)
2frequencyOf(text, ch)Required behavior:
characterFrequency(text) returns counts for all encountered characters.frequencyOf(text, ch) returns 0 when ch is absent.Your implementation will be tested with:
1text = ""
2text = "aaaa"
3text = "aA"
4text = "a a"
5frequencyOf("baba", 'z')The tested contract is: initialize counts correctly, process every index once, increment the matching character count, and return zero for an absent queried character.
1def character_frequency(text):
2 counts = {} # empty map, no counts yet
3 for i in range(len(text)):
4 ch = text[i]
5 counts[ch] = counts.get(ch, 0) + 1 # absent -> 0, then add one
6 return counts
7
8def frequency_of(text, ch):
9 return character_frequency(text).get(ch, 0)
10
11def show(counts):
12 return " ".join(f"{k}={counts[k]}" for k in sorted(counts)) # sorted only for stable output
13
14print(show(character_frequency("baba")))
15print(frequency_of("baba", "z"))
16print(show(character_frequency("aA")))
17print(show(character_frequency("a a")))1import java.util.HashMap;
2import java.util.Map;
3import java.util.TreeMap;
4
5public class Main {
6 static Map<Character, Integer> characterFrequency(String text) {
7 Map<Character, Integer> counts = new HashMap<>(); // empty map, no counts yet
8 for (int i = 0; i < text.length(); i++) {
9 char ch = text.charAt(i);
10 counts.put(ch, counts.getOrDefault(ch, 0) + 1); // absent -> 0, then add one
11 }
12 return counts;
13 }
14
15 static int frequencyOf(String text, char ch) {
16 return characterFrequency(text).getOrDefault(ch, 0);
17 }
18
19 static String show(Map<Character, Integer> counts) {
20 StringBuilder sb = new StringBuilder();
21 for (Map.Entry<Character, Integer> e : new TreeMap<>(counts).entrySet()) { // sorted only for stable output
22 if (sb.length() > 0) sb.append(' ');
23 sb.append(e.getKey()).append('=').append(e.getValue());
24 }
25 return sb.toString();
26 }
27
28 public static void main(String[] args) {
29 System.out.println(show(characterFrequency("baba")));
30 System.out.println(frequencyOf("baba", 'z'));
31 System.out.println(show(characterFrequency("aA")));
32 System.out.println(show(characterFrequency("a a")));
33 }
34}1#include <iostream>
2#include <map>
3#include <string>
4#include <unordered_map>
5using namespace std;
6
7unordered_map<char, int> characterFrequency(const string& text) {
8 unordered_map<char, int> counts; // empty map, no counts yet
9 for (size_t i = 0; i < text.size(); i++) {
10 counts[text[i]]++; // an absent key starts at 0
11 }
12 return counts;
13}
14
15int frequencyOf(const string& text, char ch) {
16 auto counts = characterFrequency(text);
17 auto it = counts.find(ch);
18 return it == counts.end() ? 0 : it->second;
19}
20
21string show(const unordered_map<char, int>& counts) {
22 map<char, int> ordered(counts.begin(), counts.end()); // sorted only for stable output
23 string out;
24 for (auto& kv : ordered) {
25 if (!out.empty()) out += ' ';
26 out += kv.first;
27 out += '=';
28 out += to_string(kv.second);
29 }
30 return out;
31}
32
33int main() {
34 cout << show(characterFrequency("baba")) << endl;
35 cout << frequencyOf("baba", 'z') << endl;
36 cout << show(characterFrequency("aA")) << endl;
37 cout << show(characterFrequency("a a")) << endl;
38}1function characterFrequency(text) {
2 const counts = new Map(); // empty map, no counts yet
3 for (let i = 0; i < text.length; i++) {
4 const ch = text[i];
5 counts.set(ch, (counts.get(ch) ?? 0) + 1); // absent -> 0, then add one
6 }
7 return counts;
8}
9
10function frequencyOf(text, ch) {
11 return characterFrequency(text).get(ch) ?? 0;
12}
13
14function show(counts) {
15 return [...counts.keys()].sort().map((k) => `${k}=${counts.get(k)}`).join(' '); // sorted only for stable output
16}
17
18console.log(show(characterFrequency('baba')));
19console.log(frequencyOf('baba', 'z'));
20console.log(show(characterFrequency('aA')));
21console.log(show(characterFrequency('a a')));Not unless the task says so. The lesson treats displayed characters as distinct, so "aA" gives a=1 and A=1. Lowercase the text first only when the problem asks for it.
Use an array when the task fixes the alphabet, such as lowercase a to z. Map each letter to an index (a is 0, z is 25) and check that every character belongs. Use a map when the characters are not bounded.
The scan visits each of the n characters once, and a hash map lookup and update are expected O(1). The O(n^2) figure appears only when collisions make every lookup cost O(n).
No. It stores counts, not positions. "ab" and "ba" give the same table, so you cannot rebuild the string from it.
Use collections.Counter(text). It builds the same character-to-count map in O(n) time. It does the same work as the loop above in one call.
The loop runs zero times and the function returns an empty map. Every query on it, such as frequencyOf("", 'a'), returns 0.