Problem

Given a string s consisting of lowercase English letters, return the frequency of every character that appears in s. Output the characters in alphabetical order, each with its count.

Input / Output

• Input: string s.
• Output: a list of (character, count) pairs sorted by character, or an array of 26 counts.

Examples

Example 1 Input: s = "banana" Output: a:3, b:1, n:2

Example 2 Input: s = "zzzz" Output: z:4

Constraints

• 1 <= s.length <= 10^5
• s contains only 'a'–'z'.

Approach

Because the alphabet is fixed and small, a counting array of size 26 is the ideal structure:

1. Create cnt[26] filled with zeros.
2. For each character c, do cnt[c - 'a']++.
3. Iterate cnt from 0 to 25 and emit the letters whose count is non-zero.

This avoids hashing overhead and produces the output already sorted.

If the input can contain arbitrary Unicode, use a hash map from character to count and sort the keys at the end (O(k log k) where k is the number of distinct characters).

Complexity

• Time: O(n + 26) = O(n)
• Space: O(26) = O(1) for the fixed alphabet; O(k) with a hash map.

Follow-ups this problem sets up

• Find the first non-repeating character (single pass to count, second pass to find count 1).
• Check whether two strings are anagrams (compare the two count arrays).
• Most frequent character, with tie-breaking rules.
• Count frequencies in a stream with a bounded memory window.

Reference solution (Python)

def char_frequency(s):
    cnt = [0] * 26
    for c in s:
        cnt[ord(c) - 97] += 1
    return [(chr(i + 97), cnt[i]) for i in range(26) if cnt[i]]

Test cases

Input	Expected
"banana"	[('a',3),('b',1),('n',2)]