Inverting a Character Frequency Map in Python

Problem Statement

Given a string containing lowercase English letters, compute the frequency of each character and then invert the mapping such that:

• Keys represent frequencies.
• Values represent a list of characters that occur with that frequency.

Example

Input

aabbccdde

Character Frequency Map

{
    'a': 2,
    'b': 2,
    'c': 2,
    'd': 2,
    'e': 1
}

Expected Output

{
    1: ['e'],
    2: ['a', 'b', 'c', 'd']
}

Understanding the Problem

Most frequency-counting problems stop after creating a dictionary that maps characters to their counts.

For this problem, we need to go one step further and invert the mapping.

Instead of:

character -> frequency

we need:

frequency -> list of characters

This pattern appears frequently in:

• Data aggregation
• Log analysis
• Grouping operations
• Feature engineering
• Text analytics

Step 1: Count Character Frequencies

We first create a dictionary to count how many times each character appears.

freq = {}
for ch in s:
    freq[ch] = freq.get(ch, 0) + 1

For the input:

aabbccdde

the resulting dictionary becomes:

{
    'a': 2,
    'b': 2,
    'c': 2,
    'd': 2,
    'e': 1
}

Step 2: Invert the Frequency Map

Now we iterate through the frequency dictionary and group characters by frequency.

result = {}
for ch, count in freq.items():
    if count not in result:
        result[count] = []
    result[count].append(ch)

After this step:

{
    2: ['a', 'b', 'c', 'd'],
    1: ['e']
}

Step 3: Sort Characters (Optional)

Sorting ensures deterministic output.

for count in result:
    result[count].sort()

This guarantees:

{
    1: ['e'],
    2: ['a', 'b', 'c', 'd']
}

instead of potentially different orders.

Step 4: Sort Frequencies

The problem requires frequency keys in ascending order.

result = dict(sorted(result.items()))

Final output:

{
    1: ['e'],
    2: ['a', 'b', 'c', 'd']
}

Complete Solution

def solve(s):
    freq = {}

    # Count frequencies
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1

    # Invert mapping
    result = {}

    for ch, count in freq.items():
        if count not in result:
            result[count] = []

        result[count].append(ch)

    # Sort character lists
    for count in result:
        result[count].sort()

    # Sort frequency keys
    result = dict(sorted(result.items()))

    return result

Dry Run

Input:

aabbccdde

Frequency Count

{
    'a': 2,
    'b': 2,
    'c': 2,
    'd': 2,
    'e': 1
}

Inverted Map

{
    1: ['e'],
    2: ['a', 'b', 'c', 'd']
}

Final Output

{
    1: ['e'],
    2: ['a', 'b', 'c', 'd']
}

Time Complexity

Frequency Counting

O(n)

where n is the length of the string.

Inversion

O(k)

where k is the number of unique characters.

Sorting

O(k log k)

in the worst case.

Overall Complexity

O(n + k log k)

Since k ≤ 26 for lowercase English letters, the solution is effectively linear for practical inputs.

Key Takeaways

1. Frequency maps are one of the most common data structures in interview problems.
2. Inverting a dictionary is a useful grouping technique.
3. Python dictionaries combined with lists make grouping operations concise and efficient.
4. The pattern used here is similar to SQL’s GROUP BY operation.

This problem is an excellent example of transforming data from one representation into another while maintaining efficiency and readability.