SyntaxPilot
Courses/Python Coding Questions/Lesson 12
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 12 of 30

String questions II

anagram check (sorted vs Counter)first non-repeating charactermost frequent character (ties)

These are the notes for Python Coding Questions, episode 12, the second round of string questions. Three classic questions that are all secretly about one skill: counting letters. Checking an anagram (and why comparing sets lies to you), finding the first character that doesn't repeat (where the simple answer is correct but takes over three seconds), and finding the most frequent character, where max() gives a confident wrong answer and ties and empty strings need care. Along the way you'll meet the frequency count, collections.Counter, the cost of sorting (O(n log n)), why s.count() inside a loop is O(n²), how to time code with time.perf_counter(), and how a key function tells max() what to compare.

Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real. Three things will differ on your machine: timings from time.perf_counter() change on every run and every computer (below is one representative run), the order a set prints in (like {'a', 'b'} or {'b', 'a'}) can change from run to run, and tracebacks show the full path to your file; here it is shortened to main.py.

Q1: Anagram check

Real-life example: magnet letters on a fridge. Someone spells LISTEN. Your little sister moves the same six magnets around, and now they say SILENT. No magnet added, none taken away. That's an anagram: the same letters, used the same number of times each, in a different order. So "aab" and "abb" are not anagrams: one has two a's, the other two b's. How many matters.

Input Output
"listen", "silent" True
"aab", "abb" False (different counts)
"chai", "chaii" False (an extra i)
"rat", "car" False
"Dormitory", "dirty room" True (ignoring capitals and spaces)
"School master", "The classroom" True
"", "" True

Ask the interviewer: do capitals count (is D the same as d)? Do spaces and punctuation count? Only English letters, or any characters? What about two empty strings?

Attempt 1: compare the sets of letters

A set is a collection of unique items: set("listen") is the letters of listen, each kept once. Same letters, same set, so let's compare the sets.

def is_anagram(a, b):
    return set(a) == set(b)

print(is_anagram("listen", "silent"))
print(is_anagram("aab", "abb"))
print(is_anagram("chai", "chaii"))

Output:

True
True
True

Why it's wrong: the first True is right. The other two are not: "aab" and "abb" have different counts, and "chaii" has an extra magnet. No error, just a wrong answer. Look at what the sets really hold:

print(set("aab"), set("abb"), set("aab") == set("abb"))
print(set("chai"), set("chaii"))
print(len("chai"), len("chaii"))
print(set("listen") == set("silent"))

Output (the order of the letters inside each {...} can change from run to run):

{'a', 'b'} {'a', 'b'} True
{'a', 'c', 'h', 'i'} {'a', 'c', 'h', 'i'}
4 5
True

A set keeps each item only once. Both "aab" and "abb" become the set {'a', 'b'}. The set remembers which letters, and forgets how many. Even the lengths (4 and 5) show chai and chaii can't be anagrams, but the sets look identical.

Attempt 2: sort the letters

Put each word's letters in order. If two words are anagrams, their sorted letters are identical, duplicates included. sorted() on a string gives a list of its characters in order.

def is_anagram(a, b):
    return sorted(a) == sorted(b)

print(sorted("listen"))
print(is_anagram("listen", "silent"), is_anagram("aab", "abb"))
print(is_anagram("Dormitory", "dirty room"))

Output:

['e', 'i', 'l', 'n', 's', 't']
True False
False

"aab" and "abb" are False now: correct, the duplicates count. But the classic puzzle, Dormitory and dirty room, is False. Look at the sorted letters:

print(sorted("silent"))
print(sorted("aab"), sorted("abb"))
print(sorted("Dormitory"))
print(sorted("dirty room"))
print(ord("D"), ord("d"), ord(" "))

Output:

['e', 'i', 'l', 'n', 's', 't']
['a', 'a', 'b'] ['a', 'b', 'b']
['D', 'i', 'm', 'o', 'o', 'r', 'r', 't', 'y']
[' ', 'd', 'i', 'm', 'o', 'o', 'r', 'r', 't', 'y']
68 100 32

Why it fails: the same trap as the palindromes in episode 11. sorted orders characters by their number code (ord()): the space is 32, capital D is 68 and small d is 100. So Dormitory starts with 'D', dirty room starts with a space and has a small 'd'. To Python they are different characters.

There's a second, quieter problem: sorting costs O(n log n). For n letters, a good sort needs about log n rounds of work over them, so n × log n steps. And we don't even need the letters in order.

The fix: clean, then count with a Counter

We only need to know how many of each letter there is. Like counting the magnets: two a's, one b. That's a frequency count: a dictionary from each item to how many times it appears. Python's collections module (part of the standard library, so nothing to install) has one ready-made: Counter.

from collections import Counter
c = Counter("aab")
print(c, c["a"], c["z"])
print(Counter("aab") == Counter("abb"))
print(Counter("aab") == Counter("aba"))
print(dict(c))

Output:

Counter({'a': 2, 'b': 1}) 2 0
False
True
{'a': 2, 'b': 1}
  • Counter("aab") walks the string once and counts: a → 2, b → 1.
  • c["z"] is 0: a Counter gives 0 for a missing key instead of raising KeyError.
  • Two Counters are equal when every item has the same count. "aab" vs "abb": different. "aab" vs "aba": the same counts, so equal.

To ignore capitals and spaces, clean both words first, with lower() and isalnum() (True for letters and digits), exactly like the palindrome check:

def clean(s):
    return [ch.lower() for ch in s if ch.isalnum()]

print(clean("Dormitory"))
print(clean("dirty room"))
print(sorted(clean("Dormitory")) == sorted(clean("dirty room")))

Output:

['d', 'o', 'r', 'm', 'i', 't', 'o', 'r', 'y']
['d', 'i', 'r', 't', 'y', 'r', 'o', 'o', 'm']
True

The capital is lowered and the space is gone. (Cleaning fixes the sorted version too; the Counter version is just faster.) The full solution from the video:

from collections import Counter

def clean(s):
    return [ch.lower() for ch in s if ch.isalnum()]

def is_anagram(a, b):
    return Counter(clean(a)) == Counter(clean(b))

print(Counter(clean("listen")))
for a, b in [("listen", "silent"), ("aab", "abb"), ("Dormitory", "dirty room"),
             ("School master", "The classroom"), ("", ""), ("chai", "chaii")]:
    print(repr(a), repr(b), "->", is_anagram(a, b))

Output:

Counter({'l': 1, 'i': 1, 's': 1, 't': 1, 'e': 1, 'n': 1})
'listen' 'silent' -> True
'aab' 'abb' -> False
'Dormitory' 'dirty room' -> True
'School master' 'The classroom' -> True
'' '' -> True
'chai' 'chaii' -> False

Every test is right. Two empty strings give two empty Counters, which are equal: True.

  • O(n) time: one pass to clean each string, one pass to count it, and comparing two Counters is one pass over their entries. O(n) extra space for the cleaned lists; the Counters hold at most one entry per different character.

Sorted vs Counter, timed

O(n log n) vs O(n) is not just theory. Two strings of a million letters:

import time
from collections import Counter

a = "abcdefghij" * 100_000
b = a[::-1]
start = time.perf_counter()
print(sorted(a) == sorted(b), round(time.perf_counter() - start, 3), "seconds (sorted)")
start = time.perf_counter()
print(Counter(a) == Counter(b), round(time.perf_counter() - start, 3), "seconds (Counter)")

Output (a representative run; your timings will differ):

True 0.125 seconds (sorted)
True 0.055 seconds (Counter)

time.perf_counter() returns a time in seconds from a very precise clock; the difference between two calls is how long the code in between took. Both answers are True; the Counter is a little over twice as fast here, and the gap grows as n grows. For short words either is fine. In an interview, mention both and say why Counter is O(n).

The follow-up: no Counter, a plain dictionary

Interviewers often add: "Now do it without Counter." Use a plain dict. Count up for each letter of a, count down for each letter of b. If any count goes below zero, b has a letter that a didn't give us. And a quick exit: if the lengths differ, they can't be anagrams.

def is_anagram(a, b):
    if len(a) != len(b):
        return False                  # quick exit
    counts = {}
    for ch in a:
        counts[ch] = counts.get(ch, 0) + 1
    for ch in b:
        counts[ch] = counts.get(ch, 0) - 1
        if counts[ch] < 0:
            return False              # b has an extra ch
    return True

print(is_anagram("listen", "silent"), is_anagram("aab", "abb"))
print(is_anagram("rat", "car"))

Output:

True False
False

counts.get(ch, 0) means "the count for ch, or 0 if ch isn't in the dictionary yet". Plain counts[ch] would crash on a new letter:

counts = {"a": 2}
print(counts.get("a", 0), counts.get("z", 0))
print(counts["z"])

Output:

2 0
Traceback (most recent call last):
  File "main.py", line 3, in <module>
    print(counts["z"])
          ~~~~~~^^^^^
KeyError: 'z'

Why is "below zero" enough? The lengths are equal. If b is not an anagram, it must have more of some letter than a (if it had fewer of one, it would need more of another to reach the same length). So some count must drop below zero.

Walking through the counts

The same function with a print after each step:

def is_anagram(a, b):
    if len(a) != len(b):
        return False
    counts = {}
    for ch in a:
        counts[ch] = counts.get(ch, 0) + 1
    print("after a:", counts)
    for ch in b:
        counts[ch] = counts.get(ch, 0) - 1
        print(f"  {ch!r} -> {counts}")
        if counts[ch] < 0:
            return False
    return True

print(is_anagram("rat", "car"))
print(is_anagram("aab", "aba"))

Output:

after a: {'r': 1, 'a': 1, 't': 1}
  'c' -> {'r': 1, 'a': 1, 't': 1, 'c': -1}
False
after a: {'a': 2, 'b': 1}
  'a' -> {'a': 1, 'b': 1}
  'b' -> {'a': 1, 'b': 0}
  'a' -> {'a': 0, 'b': 0}
True
Step Letter of b counts Action
rat/car, 1 c c: -1 rat never gave a c: below zero, False at once
aab/aba, 1 a a: 1, b: 1 fine
aab/aba, 2 b a: 1, b: 0 fine
aab/aba, 3 a a: 0, b: 0 all used up exactly: True

Rat and car have the same length, so the quick exit doesn't fire, but the very first letter of car sends c to −1. This version is case-sensitive; clean both strings first if the interviewer wants to ignore capitals and spaces.

  • O(n) time (two passes), and the dictionary holds at most one entry per different letter: for English letters that's at most 26, a small fixed number, so O(1) extra space for a fixed alphabet (O(k) for k different characters in general).

Q2: First non-repeating character

Real-life example: a line at a ration shop. Families stand in the line, but not always next to each other. The shopkeeper wants the first person in the line who came alone, with no family member anywhere else in the line. In SWISS, the three s's are one family. The first person alone is w, at position 1.

Input Output
"swiss" w (index 1)
"chai" c (index 0: every letter is unique, the first wins)
"aabb" none: -1 / None
"" none: -1 / None
"Aa" A (index 0, if capitals are different characters)

Ask the interviewer: should I return the character or its index? Does case matter (is A the same as a)? What should I return when every character repeats, or the string is empty?

Attempt: s.count(ch) for every letter

Walk along the line, and for each person, count how many of their family are in the whole line. The first one with a count of 1 is the answer.

def first_unique(s):
    for ch in s:
        if s.count(ch) == 1:
            return ch

print(first_unique("swiss"), first_unique("chai"), first_unique("aabb"))

Output:

w c None

All three are correct. "aabb" gives None: every letter repeats, so the loop ends without a return, and a Python function that finishes without return gives back None:

def first_unique(s):
    for ch in s:
        if s.count(ch) == 1:
            return ch

result = first_unique("aabb")
print(result, result is None)

Output:

None True

Here is what s.count(ch) finds for each letter of "swiss". (enumerate(s) gives each index together with its character.)

s = "swiss"
for i, ch in enumerate(s):
    print(i, ch, s.count(ch))

Output:

0 s 3
1 w 1
2 i 1
3 s 3
4 s 3

So what's wrong? Let's try a long line: the pattern ab fifty thousand times, and a single z at the very end. We time it with time.perf_counter().

import time

def first_unique(s):
    for ch in s:
        if s.count(ch) == 1:
            return ch

s = "ab" * 50_000 + "z"            # 100,001 letters, z at the end
start = time.perf_counter()
print(first_unique(s))
print(round(time.perf_counter() - start, 2), "seconds")

Output (a representative run; the time varies by machine and run, the video's run took 3.21 seconds):

z
3.41 seconds

z is the right answer, but it took over three seconds for a string of a hundred thousand letters. (50_000 is just 50000; underscores in numbers are allowed to make them easier to read.)

Why it's slow: s.count(ch) is not free. It walks the whole string every time it's called, n steps. And we call it for every letter until we find the answer. Here that's 100,000 letters × 100,001 steps each: about ten billion character checks. That's O(n²): double the length and the time goes up about four times. Correct code, wrong complexity.

The fix: count once, then a second pass

Counting inside the loop is the problem. Each count is a full walk of the line. Instead:

  1. Pass 1: count every family once, up front: counts = Counter(s). One walk.
  2. Pass 2: walk the line again, in order, and return the first person whose count is 1. Looking up a count in a dictionary is O(1) on average: instant.
import time
from collections import Counter

def first_unique(s):
    counts = Counter(s)          # pass 1: count every letter
    for i, ch in enumerate(s):   # pass 2: first with count 1
        if counts[ch] == 1:
            return i, ch
    return -1, None              # no unique letter

for s in ["swiss", "chai", "aabb", "", "Aa"]:
    print(repr(s), first_unique(s))

s = "ab" * 50_000 + "z"
start = time.perf_counter()
print(first_unique(s), round(time.perf_counter() - start, 3), "seconds")

Output (the time is a representative run and will differ on your machine):

'swiss' (1, 'w')
'chai' (0, 'c')
'aabb' (-1, None)
'' (-1, None)
'Aa' (0, 'A')
(100000, 'z') 0.006 seconds
  • swiss: index 1, w. chai: index 0, c.
  • aabb and the empty string: (-1, None). −1 is the usual "not found" index (like str.find), because 0 is a real index.
  • "Aa": index 0, A, because capital A and small a are different characters. If the interviewer says case doesn't matter, count s.lower() instead.
  • The long string: z at index 100,000 in a few thousandths of a second. Hundreds of times faster than before.

The function returns a tuple (index, character); return i, ch builds it without brackets.

Walking through the two passes

from collections import Counter

s = "swiss"
counts = Counter(s)
print(counts)
for i, ch in enumerate(s):
    print(f"i={i} ch={ch!r} counts[ch]={counts[ch]}")
    if counts[ch] == 1:
        print("answer:", i, ch)
        break

Output:

Counter({'s': 3, 'w': 1, 'i': 1})
i=0 ch='s' counts[ch]=3
i=1 ch='w' counts[ch]=1
answer: 1 w
Pass What happens Result
1 Counter("swiss") walks all 5 letters once s: 3, w: 1, i: 1
2, i = 0 s: count 3, it has family skip
2, i = 1 w: count 1, came alone answer (1, 'w')

The letter i at index 2 is never checked: the second pass stops at the first match. Why pass 2 walks the string, not the Counter: the string keeps the line order. (A Counter also remembers the order keys were first added, so next over its items would work too; walking the string says what you mean.)

  • O(n) time: O(n) for pass 1 plus O(n) for pass 2 is 2n steps, and O() drops the constant 2. O(1) extra space for a fixed alphabet (one entry per different character, O(k) in general).

Q3: Most frequent character, with ties

Real-life example: electing a class monitor. The teacher writes each name on the board and adds a tally mark for each vote: Asha |||, Ravi ||. The name with the most marks wins, not the name that comes last in the alphabet. That sounds silly, but remember it. And if two names have the same number of votes, it's a tie: a fair teacher doesn't quietly pick one. The question says the same: return every tied character.

Input Output
"banana" ['a'] (a: 3)
"mississippi" ['i', 's'] (both 4: a tie)
"to be or not to be" ['o'] (letters only: o: 4)
"abab" and "baba" ['a', 'b'] for both
"" and "!!" [] (nothing to count)

Ask the interviewer: count letters only, or spaces and punctuation too? Does case matter? On a tie, return one character (which one?) or all of them? What should an empty string return?

Attempt 1: max(counts)

Count the letters in a dictionary, the same way as Q1, then take the maximum.

def most_frequent(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return max(counts)

print(most_frequent("banana"))
print(most_frequent("mississippi"))

Output:

n
s

Why it's wrong: banana has three a's and only two n's, yet the answer is n. No error, a confident wrong answer.

max() of a dictionary looks only at its keys. Looping over a dict gives its keys, so max(counts) is the same as max(["b", "a", "n"]): the largest letter, and n comes after a and b in the alphabet. It never looked at the counts at all. The name last in the alphabet won the election.

counts = {"b": 1, "a": 3, "n": 2}
print(max(counts), list(counts))
print(max(["b", "a", "n"]))
print(max(counts.values()))
print(max(counts, key=counts.get))
print(counts.get("a"), counts.get("n"))

Output:

n ['b', 'a', 'n']
n
3
a
3 2

max(counts.values()) compares the counts and gives 3, but that's the number, not the letter. To get the letter with the highest count, we need a key function.

Attempt 2: max(counts, key=counts.get)

A key function tells max() (and min(), sorted()) what to compare. With key=counts.get, max still goes over the keys, but for each letter it calls counts.get(letter) and compares those numbers: a → 3, n → 2. It returns the letter, not the number. Note there are no brackets: counts.get passes the method itself, for max to call.

def most_frequent(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return max(counts, key=counts.get)

print(most_frequent("banana"), most_frequent("mississippi"))
print(repr(most_frequent("to be or not to be")))
print(most_frequent("abab"), most_frequent("baba"))
print(most_frequent(""))

Output:

a i
' '
a b
Traceback (most recent call last):
  File "main.py", line 10, in <module>
    print(most_frequent(""))
          ~~~~~~~~~~~~~^^^^
  File "main.py", line 5, in most_frequent
    return max(counts, key=counts.get)
ValueError: max() iterable argument is empty

a for banana: correct. But four new problems:

  1. Mississippi gives only i. It has four i's and four s's: a tie, and we got one of them.
  2. "to be or not to be" is won by a space. Five spaces, only four o's. Spaces are characters too:
from collections import Counter
print(Counter("to be or not to be"))

Output:

Counter({' ': 5, 'o': 4, 't': 3, 'b': 2, 'e': 2, 'r': 1, 'n': 1})
  1. The order decides a tie. "abab" gives a, "baba" gives b: the same votes, a different winner. When counts are equal, max keeps the first one it sees, and a dict keeps keys in the order they were first added:
counts_abab = {"a": 2, "b": 2}
counts_baba = {"b": 2, "a": 2}
print(max(counts_abab, key=counts_abab.get), max(counts_baba, key=counts_baba.get))
print(min([3, 1, 1]), min(["chai", "tea"], key=len))

Output:

a b
1 tea

(min works the same way: min(["chai", "tea"], key=len) compares the lengths and gives the shorter word.)

  1. The empty string crashes: ValueError: max() iterable argument is empty. A ValueError means the type of the argument is right but its value can't be used. There are no votes, so there is no maximum. max() has a default= for this case:
print(max([], default=None))
print(max({}))

Output:

None
Traceback (most recent call last):
  File "main.py", line 2, in <module>
    print(max({}))
          ~~~^^^^
ValueError: max() iterable argument is empty

The fix: a fair election in four steps

  1. Count letters only, lowered: ch.isalpha() is True only for letters (not digits, spaces or punctuation), and ch.lower() makes capital A and small a one candidate.
  2. Nothing counted? Return [] before max() can crash.
  3. top = max(counts.values()): the highest count. Now max compares numbers, the vote counts.
  4. Every letter whose count equals top, sorted, so the answer doesn't depend on the order of the string.
for ch in "aZ3 !é_":
    print(repr(ch), ch.isalpha(), ch.isalnum())

Output:

'a' True True
'Z' True True
'3' False True
' ' False False
'!' False False
'é' True True
'_' False False

isalpha() is letters only; isalnum() is letters and digits. Both say False for spaces, punctuation and _, and both accept é (a letter, just not an English one). The full solution from the video:

from collections import Counter

def most_frequent(s):
    counts = Counter(ch.lower() for ch in s if ch.isalpha())
    if not counts:
        return []                        # nothing to count
    top = max(counts.values())
    return sorted(ch for ch, n in counts.items() if n == top)

for s in ["banana", "mississippi", "to be or not to be",
          "abab", "baba", "", "!!"]:
    print(repr(s), most_frequent(s))

print(Counter("mississippi").most_common(2))

Output:

'banana' ['a']
'mississippi' ['i', 's']
'to be or not to be' ['o']
'abab' ['a', 'b']
'baba' ['a', 'b']
'' []
'!!' []
[('i', 4), ('s', 4)]
  • banana: a. mississippi: i and s. to be or not to be: o; the spaces don't vote any more.
  • "abab" and "baba" now give the same answer: ['a', 'b'].
  • The empty string and "!!" give [], and no crash. if not counts: works because an empty Counter is falsy.
  • counts.items() gives (letter, count) pairs, so for ch, n in counts.items() unpacks each pair.

Walking through Mississippi

from collections import Counter

s = "Mississippi"
counts = Counter(ch.lower() for ch in s if ch.isalpha())
print(counts)
top = max(counts.values())
print(top)
print([ch for ch, n in counts.items() if n == top])
print(sorted(ch for ch, n in counts.items() if n == top))

Output:

Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})
4
['i', 's']
['i', 's']
Step Code Value
1 Counter(...) of the lowered letters i: 4, s: 4, p: 2, m: 1 (capital M became m)
2 if not counts not empty, carry on
3 max(counts.values()) 4
4 letters with count 4, sorted ['i', 's']

Counter.most_common

most_common(k) gives the top k items as (item, count) pairs, highest count first; with no argument, all of them.

from collections import Counter
c = Counter("mississippi")
print(c.most_common())
print(c.most_common(1), c.most_common(2))
print(Counter("abab").most_common(1), Counter("baba").most_common(1))

Output:

[('i', 4), ('s', 4), ('p', 2), ('m', 1)]
[('i', 4)] [('i', 4), ('s', 4)]
[('a', 2)] [('b', 2)]

Handy, but it lists ties in the order they were first seen, so most_common(1) has the same tie problem as max: "abab" gives a, "baba" gives b. For a tie you still check the counts yourself, like the four-step fix.

  • O(n) time: one pass to count, one pass over the counts (at most n entries), and the sort is over the tied letters only (at most 26 for English letters). O(1) extra space for a fixed alphabet: at most 26 entries.

Common mistakes (and what you really see)

Mistake What you see Why Fix
set(a) == set(b) for anagrams "aab", "abb" → True a set forgets how many Counter(a) == Counter(b)
sorted(a) == sorted(b) on phrases "Dormitory", "dirty room" → False 'D' != 'd', the space counts lower() + isalnum() first
counts[ch] += 1 on a new key KeyError: 'b' the key isn't in the dict yet counts.get(ch, 0) + 1, or Counter
counts["z"] on a missing letter KeyError: 'z' plain dicts don't default to 0 counts.get("z", 0)
if s.count(ch) == 1 in a loop 3.41 seconds for 100,001 letters (varies) count walks the whole string each time: O(n²) Counter first, then one pass
returning 0 for "not found" can't tell "not found" from index 0 0 is a real index return -1 (or None)
max(counts) banana → 'n' compares the keys, not the counts max(counts, key=counts.get)
max(counts.values()) alone 3 the highest count, not the letter key=counts.get, or filter by top
counting every character ' ' wins "to be or not to be" spaces are characters too count ch.isalpha() only
max / most_common(1) on a tie "abab" → a, "baba" → b the first one seen wins return every letter with the top count
max() on an empty dict ValueError: max() iterable argument is empty no votes, no maximum if not counts: return [], or max(..., default=None)
a list as a dict key TypeError: unhashable type: 'list' lists can change, so they can't be keys use a tuple or a string

Your turn: group the anagrams (solution)

Put words that are anagrams of each other in one group. ["eat", "tea", "tan", "ate", "nat"] becomes [["eat", "tea", "ate"], ["tan", "nat"]].

Solution

The hint from the video: what's exactly the same for every word in one group? Their sorted letters. Every anagram of eat sorts to "aet". Use that as a dictionary key:

words = ["eat", "tea", "tan", "ate", "nat"]
for w in words:
    print(w, "->", "".join(sorted(w)))

Output:

eat -> aet
tea -> aet
tan -> ant
ate -> aet
nat -> ant

sorted(w) is a list, and a list can't be a dictionary key, so "".join(...) glues it back into a string. Then each word goes into the list for its key:

def group_anagrams(words):
    groups = {}
    for w in words:
        key = "".join(sorted(w))          # "tea" -> "aet"
        groups.setdefault(key, []).append(w)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat"]))
print(group_anagrams(["aab", "abb", "bab", "aba"]))
print(group_anagrams([""]), group_anagrams([]))

Output:

[['eat', 'tea', 'ate'], ['tan', 'nat']]
[['aab', 'aba'], ['abb', 'bab']]
[['']] []

groups.setdefault(key, []) returns the list for key, creating an empty one first if the key is new; .append(w) adds the word to it. Groups come out in the order their first word appeared. The empty string is one group of its own; an empty list of words gives no groups.

The trap, one more time: a set as the key (frozenset, a set that can't change, so it is allowed as a key) puts non-anagrams together:

def group_anagrams(words):
    groups = {}
    for w in words:
        key = frozenset(w)                # a set as the key: the set trap again
        groups.setdefault(key, []).append(w)
    return list(groups.values())

print(group_anagrams(["aab", "abb", "bab", "aba"]))

Output:

[['aab', 'abb', 'bab', 'aba']]

All four in one group, because all four have the set {a, b}.

The O(n) key: instead of sorting each word (O(k log k) for a word of k letters), count its letters into 26 slots and use the counts as the key. A list can't be a key, so turn it into a tuple (a list that can't change):

def key_of(w):
    counts = [0] * 26
    for ch in w:
        counts[ord(ch) - ord("a")] += 1
    return tuple(counts)                  # a list can't be a key; a tuple can

def group_anagrams(words):
    groups = {}
    for w in words:
        groups.setdefault(key_of(w), []).append(w)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat"]))
print(key_of("tea")[:5], key_of("tea") == key_of("ate"))

Output:

[['eat', 'tea', 'ate'], ['tan', 'nat']]
(1, 0, 0, 0, 1) True

ord(ch) - ord("a") turns a into slot 0, b into 1, ..., z into 25. For tea, slot 0 (a) and slot 4 (e) are 1. This version assumes lowercase English letters only. Trying a list as a key shows why the tuple is needed:

groups = {}
groups[[1, 2]] = "x"

Output:

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    groups[[1, 2]] = "x"
    ~~~~~~^^^^^^^^
TypeError: unhashable type: 'list'

A dictionary key must be hashable: Python computes a number (a hash) from it to find its slot, so it must never change. Strings and tuples are hashable; lists are not.

For n words of up to k letters: the sorted key is O(n · k log k) time, the counting key O(n · k). Both use O(n · k) space to hold the groups.

Practice questions (with solutions)

1. First character that repeats. "abcba" → b, "programming" → r, "chai" → None. The opposite of Q2.

Solution

First ask what "first" means. (a) The first time, reading left to right, that you meet a letter you've already seen: in "abcba" that's b (at index 3; a repeats only at index 4). (b) The first letter that appears more than once anywhere: in "abcba" that's a. Most interviewers mean (a).

For (a), one pass with a set of letters seen so far (here a set is exactly right: we only need "seen or not", not how many):

def first_repeat(s):
    seen = set()
    for ch in s:
        if ch in seen:
            return ch          # the first time any letter shows up again
        seen.add(ch)
    return None

for s in ["abcba", "swiss", "chai", "programming", ""]:
    print(repr(s), first_repeat(s))

Output:

'abcba' b
'swiss' s
'chai' None
'programming' r
'' None

For (b), Q2's two passes with > 1 instead of == 1:

from collections import Counter

def first_with_duplicate(s):
    counts = Counter(s)
    for ch in s:
        if counts[ch] > 1:
            return ch          # the first letter that appears more than once anywhere
    return None

for s in ["abcba", "swiss", "chai", "programming", ""]:
    print(repr(s), first_with_duplicate(s))

Output:

'abcba' a
'swiss' s
'chai' None
'programming' r
'' None

Only "abcba" differs, which is why you ask. Both are O(n) time and O(1) extra space for a fixed alphabet. Version (a) can stop early, without reading the whole string.

2. Is s a permutation of a palindrome? Can its letters be rearranged into a palindrome? "carrace" → True (racecar), "Tact Coa" → True (taco cat), "chai" → False.

Solution

A permutation is a rearrangement of the same items. In a palindrome, letters pair up around the middle: every letter appears an even number of times, except at most one letter (the middle one) that may appear an odd number of times. So count the letters and count how many counts are odd.

from collections import Counter
for s in ["carrace", "chai"]:
    c = Counter(s)
    print(s, dict(c), [ch for ch, n in c.items() if n % 2 == 1])

Output:

carrace {'c': 2, 'a': 2, 'r': 2, 'e': 1} ['e']
chai {'c': 1, 'h': 1, 'a': 1, 'i': 1} ['c', 'h', 'a', 'i']

carrace has one odd letter (e, the middle of racecar); chai has four. The full solution, ignoring case and spaces:

from collections import Counter

def can_be_palindrome(s):
    counts = Counter(ch.lower() for ch in s if ch.isalnum())
    odd = sum(1 for n in counts.values() if n % 2 == 1)
    return odd <= 1

for s in ["carrace", "Tact Coa", "aabb", "chai", "a", ""]:
    print(repr(s), can_be_palindrome(s))

Output:

'carrace' True
'Tact Coa' True
'aabb' True
'chai' False
'a' True
'' True

n % 2 == 1 means "n is odd" (% is the remainder). "aabb" can be abba. O(n) time, O(1) extra space for a fixed alphabet. No need to build any rearrangement.

3. Top 3 most common words in a sentence. "Chai, chai, CHAI! Tea or chai? Tea, please. Or coffee." → chai 4, then tea 2 and or 2.

Solution

Counter counts any items, not just letters: give it a list of words and it counts words. But first, the trap:

from collections import Counter
print(Counter("Chai, chai, CHAI! Tea or chai?".split()).most_common(3))

Output:

[('Chai,', 1), ('chai,', 1), ('CHAI!', 1)]

"Chai,", "chai," and "CHAI!" are three different strings. Lower the sentence, split it into words, and strip punctuation from each word:

from collections import Counter

def top_words(sentence, k=3):
    words = []
    for w in sentence.lower().split():
        w = "".join(ch for ch in w if ch.isalnum())   # "chai," -> "chai"
        if w:
            words.append(w)
    return Counter(words).most_common(k)

print(top_words("Chai, chai, CHAI! Tea or chai? Tea, please. Or coffee."))
print(top_words("the cat and the hat and the bat"))
print(top_words("hello"), top_words(""))

Output:

[('chai', 4), ('tea', 2), ('or', 2)]
[('the', 3), ('and', 2), ('cat', 1)]
[('hello', 1)] []

if w: skips a "word" that was only punctuation. With fewer than 3 different words, most_common(3) just gives what there is. Note the ties: cat, hat and bat all have 1, and most_common picks cat because it was seen first. If the interviewer wants ties broken alphabetically, sort the pairs yourself by count (highest first) and then by word:

from collections import Counter

def top_words_fair(sentence, k=3):
    counts = Counter(sentence.lower().split())
    return sorted(counts.items(), key=lambda pair: (-pair[1], pair[0]))[:k]

print(top_words_fair("b a c b a c d"))
print(Counter("b a c b a c d".split()).most_common(3))

Output:

[('a', 2), ('b', 2), ('c', 2)]
[('b', 2), ('a', 2), ('c', 2)]

The key (-pair[1], pair[0]) is a tuple: tuples compare item by item, so the negative count puts the highest first, and the word breaks ties. A lambda is a small function written in one expression. O(n) time to count (n characters), plus O(w log w) to sort w different words in the fair version.

4. Find every anagram of p inside s. s = "cbaebabacd", p = "abc" → [0, 6] ("cba" starts at 0, "bac" at 6).

Solution

Brute force: check every piece of s with the length of p:

s, k = "cbaebabacd", 3
for start in range(len(s) - k + 1):
    print(start, s[start:start + k], sorted(s[start:start + k]) == sorted("abc"))

Output:

0 cba True
1 bae False
2 aeb False
3 eba False
4 bab False
5 aba False
6 bac True
7 acd False

That re-sorts k letters at every position: O(n · k log k).

Sliding window: keep a Counter of the current window of k letters. Moving one step right, one letter comes in and one leaves, so update just those two counts instead of recounting.

from collections import Counter

def find_anagrams(s, p):
    k = len(p)
    need = Counter(p)
    window = Counter(s[:k])                # the first k letters
    result = [0] if window == need else []
    for i in range(k, len(s)):
        window[s[i]] += 1                  # letter coming in on the right
        window[s[i - k]] -= 1              # letter leaving on the left
        if window == need:
            result.append(i - k + 1)       # where this window starts
    return result

print(find_anagrams("cbaebabacd", "abc"))
print(find_anagrams("abab", "ab"))
print(find_anagrams("chai", "xyz"), find_anagrams("ab", "abc"))

Output:

[0, 6]
[0, 1, 2]
[] []

When a letter leaves, its count can drop to 0. Since Python 3.10, Counter equality treats a 0 count the same as a missing key, so the comparison still works:

from collections import Counter
c = Counter("ab")
c["b"] -= 1
print(c, c == Counter("a"))

Output:

Counter({'a': 1, 'b': 0}) True

If p is longer than s, the loop never runs and the first window isn't a match: []. Each step is O(1) work plus a Counter comparison of at most 26 entries for English letters: O(n) time, O(1) extra space for a fixed alphabet.

5. Minimum deletions to make two strings anagrams. "chai" and "chat" → 2 (delete i from one, t from the other).

Solution

Every letter one string has more of than the other must be deleted. Counter subtraction does exactly this: ca - cb keeps only the positive differences.

from collections import Counter

def deletions_to_anagram(a, b):
    ca, cb = Counter(a), Counter(b)
    extra_in_a = ca - cb        # letters a has more of
    extra_in_b = cb - ca        # letters b has more of
    return sum(extra_in_a.values()) + sum(extra_in_b.values())

print(Counter("chai") - Counter("chat"), Counter("chat") - Counter("chai"))
print(deletions_to_anagram("chai", "chat"))
print(deletions_to_anagram("listen", "silent"), deletions_to_anagram("abc", ""))

Output:

Counter({'i': 1}) Counter({'t': 1})
2
0 3

chai has an extra i, chat an extra t: 2 deletions, leaving cha and cha. Anagrams need 0; against the empty string, everything goes. O(n) time, O(1) extra space for a fixed alphabet.

Quick quiz

What does this print?

d = {"chai": 5, "tea": 9, "coffee": 2}
print(max(d), max(d, key=d.get))

(A) tea tea (B) tea coffee (C) chai tea (D) coffee tea

Answer

(A).

tea tea
  • max(d) compares the keys as strings, alphabetically: "tea" is the largest because t comes after c (both chai and coffee start with c).
  • max(d, key=d.get) compares the values: tea has 9, the most.

The same answer for two different reasons. That's why the max(dict) bug is so easy to miss: on some inputs it happens to be right. You can check each part:

d = {"chai": 5, "tea": 9, "coffee": 2}
print(sorted(d), max(d.values()), min(d, key=d.get))

Output:

['chai', 'coffee', 'tea'] 9 coffee

Interview questions

  1. How do you check whether two strings are anagrams? Counter(a) == Counter(b), after cleaning with lower() and isalnum() if case and spaces shouldn't count: O(n). Or sorted(a) == sorted(b): O(n log n). Or a plain dict that counts up for a and down for b, with a length check first.
  2. Why is set(a) == set(b) wrong for anagrams? A set keeps each item once, so it forgets how many: "aab" and "abb" both become {'a', 'b'}.
  3. What is a frequency count? A mapping from each item to how many times it appears, such as {'a': 2, 'b': 1} for "aab". In Python: a dict with counts.get(ch, 0) + 1, or collections.Counter.
  4. What does Counter give you over a plain dict? It counts an iterable in one call, returns 0 for missing keys instead of KeyError, has most_common(k), and supports + and - between Counters.
  5. Why is s.count(ch) inside a loop slow? Each count walks the whole string, O(n), and it runs for each of the n letters: O(n²). On 100,001 letters it took over three seconds; counting once with a Counter and then making a second pass took a few milliseconds.
  6. First non-repeating character? Pass 1: counts = Counter(s). Pass 2: walk s in order (with enumerate for the index) and return the first ch with counts[ch] == 1; return -1 (or None) if there is none. O(n) time, O(1) extra space for a fixed alphabet.
  7. What does max(counts) return for a dict? The largest key, because iterating a dict gives its keys. For the key with the largest value, use max(counts, key=counts.get).
  8. What does key= do in max, min and sorted? It gives a function that turns each item into the value to compare. The original item is still what's returned: min(["chai", "tea"], key=len) returns "tea".
  9. How do you handle ties for the most frequent character? Find top = max(counts.values()), then return every item whose count is top, sorted so the answer doesn't depend on the string's order. max and most_common(1) silently pick the first one seen.
  10. What happens with max() on an empty sequence? ValueError: max() iterable argument is empty. Check first (if not counts:) or pass default=.
  11. Group anagrams? Use "".join(sorted(w)) (or a tuple of 26 letter counts) as a dictionary key and append each word to its key's list. O(n · k log k) with sorting, O(n · k) with counting.

Glossary

Term Meaning Example
Anagram A word made from exactly the same letters, the same number of times each, in a different order "listen" / "silent"
Set A collection of unique items with O(1) average lookup; it forgets how many set("aab") → {'a', 'b'}
frozenset A set that can't change, so it can be a dictionary key frozenset("aab")
sorted() Returns a new sorted list of the items sorted("tea") → ['a', 'e', 't']
ord() A character's number code; sorting and comparing use it ord("D") → 68, ord("d") → 100
Frequency count A mapping from each item to how many times it appears {'a': 2, 'b': 1}
Dictionary (dict) Maps keys to values with O(1) average lookup counts["a"]
dict.get(k, default) The value for k, or default if k is missing (no KeyError) counts.get(ch, 0) + 1
KeyError A dict was asked for a key it doesn't have KeyError: 'z'
setdefault(k, v) Returns the value for k, first setting it to v if k is missing groups.setdefault(key, []).append(w)
collections module A standard-library module of extra container types from collections import Counter
Counter A dict that counts things; missing keys give 0 Counter("aab") → Counter({'a': 2, 'b': 1})
most_common(k) The top k (item, count) pairs, highest first; ties in first-seen order Counter("mississippi").most_common(2)
Counter subtraction c1 - c2 keeps only the positive differences Counter("chai") - Counter("chat") → Counter({'i': 1})
Hashable Can be a dict key or set item: a hash can be computed and it never changes strings, tuples; not lists
TypeError: unhashable type You used a changeable object, like a list, as a key groups[[1, 2]]
Tuple A fixed, unchangeable sequence; hashable, so it can be a key (1, 0, 0, 0, 1)
isalpha() True for letters only "3".isalpha() → False
isalnum() True for letters and digits "3".isalnum() → True, " ".isalnum() → False
lower() Returns a lowercase copy "Dormitory".lower() → 'dormitory'
Cleaning Keeping only the characters that count, lowered [ch.lower() for ch in s if ch.isalnum()]
s.count(x) How many times x appears in s; walks the whole string, O(n) "swiss".count("s") → 3
enumerate Gives (index, value) pairs while looping list(enumerate("chai")) → [(0, 'c'), ...]
Two passes Walk the data twice: first to count, then to find the answer Q2's Counter + second loop
None Python's "no value"; a function with no return gives it first_unique("aabb") → None
−1 for "not found" The usual "no index" answer, because 0 is a real index (-1, None)
time.perf_counter() A precise clock in seconds; subtract two readings to time code (results vary per run) time.perf_counter() - start
50_000 Underscores in a number, only for readability 50_000 == 50000
max() / min() The largest / smallest item; on a dict, compares the keys max({"b": 1, "n": 2}) → 'n'
Key function A function that turns each item into the value to compare max(counts, key=counts.get)
max/min with key Compares key(item) but returns the item itself min(["chai", "tea"], key=len) → 'tea'
default= What max/min return for an empty input instead of crashing max([], default=None)
ValueError The argument's type is right but its value can't be used max() iterable argument is empty
Tie Two or more items share the top count i and s in mississippi
dict.items() The (key, value) pairs of a dict for ch, n in counts.items()
.values() Just the values of a dict max(counts.values()) → 4
Truthy / falsy Values that count as True / False; an empty dict or Counter is falsy if not counts:
Lambda A small one-expression function lambda pair: (-pair[1], pair[0])
Permutation A rearrangement of the same items "racecar" is a permutation of "carrace"
% (remainder) What's left after division; n % 2 == 1 means n is odd 5 % 2 → 1
Sliding window A fixed-size range moved one step at a time, updating only what enters and leaves practice 4
O(n) Time or space that grows in step with n Counter(s)
O(n log n) n times log n: the cost of a good sort sorted(a) == sorted(b)
O(n²) Grows like n × n: double n, four times the work s.count(ch) inside a loop
O(1) Doesn't grow with n a dict lookup; 26 letter counts
Brute force Try every possibility re-sort every window in practice 4

Summary

  • Anagram check: set(a) == set(b) is wrong because a set forgets how many ("aab", "abb" → True). sorted(a) == sorted(b) is right but O(n log n), and fails on "Dormitory" / "dirty room" until you clean with lower() and isalnum(). The best answer: clean, then Counter(a) == Counter(b), O(n). Without Counter: a dict that counts up for a and down for b, with a length check first.
  • First non-repeating character: s.count(ch) in a loop is correct but O(n²): over three seconds on 100,001 letters. Count once with a Counter, then walk the string again in order and return the first character with count 1, in a few milliseconds. Return -1 / None when there is none, and ask whether case matters.
  • Most frequent character: max(counts) compares the keys (banana → n). max(counts, key=counts.get) compares the counts, but counts spaces, lets the order pick a tie winner, and crashes on empty input with ValueError. Count letters only, lowered; return [] if nothing was counted; find the top count; return every tied letter, sorted. O(n) time.

Next episode: String questions III: capitalizing every word (and the title() trap), converting camelCase to snake_case, and counting words when there are extra spaces.