Find character frequencies in a word without collection classes
Filed under Morgan Stanley
Free read 1 of 3Ask about the character set (ASCII or Unicode), case sensitivity and the output order. A fixed-size array indexed by character code works for ASCII.
The question
Given a word, print how many times each character occurs, without using any collection class such as a map, set or Counter. Use a plain array for counting.
Constraints
- No Map, Set or Counter allowed; arrays and strings only
- Assume ASCII characters
- Target O(n) time
Examples
- Input
- hello
- Output
- h1e1l2o1
- Why
- l appears twice; others once, in first-appearance order
- Input
- aab
- Output
- a2b1
- Why
- a appears twice, b once
Approach
Ask about the character set (ASCII or Unicode), case sensitivity and the output order. A fixed-size array indexed by character code works for ASCII.
For each character, scan the whole word to count it and skip characters already counted. This is O(n^2) and needs a way to mark duplicates.
Use an int array of size 256 indexed by the character code. One pass counts everything; a second pass prints each character the first time it is seen and resets its count.
Empty string, repeated single character, mixed case and non-ASCII input (use a larger array or a hash map if allowed).
Solution
O(n) time, O(1) space
def char_freq(word):
counts = [0] * 256 # direct-address table instead of a map
for ch in word:
counts[ord(ch)] += 1
out = ""
for ch in word:
n = counts[ord(ch)]
if n: # first time we see this character
out += ch + str(n)
counts[ord(ch)] = 0 # reset so it is reported once
return out
Tips
- What they are testing: Tests whether you can replace a map with a direct-address table and keep the solution O(n) time with O(1) extra space.
- Common mistake: Nested loops that recount characters, or printing a character's count more than once.
Related Morgan Stanley questions
Collected from public candidate posts and coding forums. Updated Nov 2026.