Katkat
Back

Character Frequency Count in a String

AntraSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate strings and utilize hash maps to count character frequencies while maintaining the original order of character appearance.

Problem Statement

Given a string s, write a function that returns a list of tuples (or an equivalent structure), where each tuple contains a character from the string and its total frequency count. The results must be ordered by the first appearance of each character in the string.

Your implementation should be case-sensitive (i.e., 'A' and 'a' are distinct characters). You should ignore non-alphabetic characters if they are present, or treat them as characters to be counted based on the following rules: treat all characters as valid tokens, including spaces and punctuation.

Function Signature

def get_character_frequencies(s: str) -> list[tuple[str, int]]

Examples

Example 1: Input: s = "hello" Output: [('h', 1), ('e', 1), ('l', 2), ('o', 1)] Explanation: 'h' appears first, then 'e', then 'l' (twice), then 'o'.

Example 2: Input: s = "AaBb" Output: [('A', 1), ('a', 1), ('B', 1), ('b', 1)] Explanation: Case sensitivity is maintained, so 'A' and 'a' are separate entries.

Constraints

  • 0 <= len(s) <= 10^6
  • The string can contain any Unicode character.
  • You should aim for O(n) time complexity where n is the length of the string.

Edge Cases

  • Empty string: return an empty list.
  • String with only one character repeated multiple times.
  • String with spaces and special characters.

Hints

Hint 1

Consider using a hash map (dictionary) to store the counts of each character as you iterate through the string.

Hint 2

Since standard dictionaries in modern versions of many languages (like Python 3.7+) preserve insertion order, you can use the dictionary to track both the count and the order of appearance.

Hint 3

If the language you are using does not guarantee dictionary insertion order, consider using an auxiliary list to keep track of the unique characters in the order they were first encountered.

Follow-up questions

  • How would you modify your solution to make it case-insensitive (e.g., 'A' and 'a' are treated as the same character)?
  • If memory were extremely limited and the alphabet was restricted to ASCII, how would you optimize space complexity?
  • How would you handle a scenario where the input string is too large to fit into memory all at once, such as a continuous stream of characters?