โ† Morgan Stanley questions

Find character frequencies in a word without collection classes

Filed under Morgan Stanley

Free read 1 of 3

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.

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

  1. 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.

Solution

O(n) time, O(1) space

Python
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.