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"]is0: aCountergives 0 for a missing key instead of raisingKeyError.- 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:
- Pass 1: count every family once, up front:
counts = Counter(s). One walk. - 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.aabband the empty string:(-1, None). −1 is the usual "not found" index (likestr.find), because 0 is a real index."Aa": index 0,A, because capitalAand smallaare different characters. If the interviewer says case doesn't matter, counts.lower()instead.- The long string:
zat 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:
- Mississippi gives only
i. It has four i's and four s's: a tie, and we got one of them. - "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})
- The order decides a tie.
"abab"givesa,"baba"givesb: the same votes, a different winner. When counts are equal,maxkeeps 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.)
- The empty string crashes:
ValueError: max() iterable argument is empty. AValueErrormeans 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 adefault=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
- Count letters only, lowered:
ch.isalpha()is True only for letters (not digits, spaces or punctuation), andch.lower()makes capitalAand smallaone candidate. - Nothing counted? Return
[]beforemax()can crash. top = max(counts.values()): the highest count. Nowmaxcompares numbers, the vote counts.- 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:iands. 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, sofor 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 becausetcomes afterc(bothchaiandcoffeestart withc).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
- How do you check whether two strings are anagrams?
Counter(a) == Counter(b), after cleaning withlower()andisalnum()if case and spaces shouldn't count: O(n). Orsorted(a) == sorted(b): O(n log n). Or a plain dict that counts up foraand down forb, with a length check first. - 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'}. - 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: adictwithcounts.get(ch, 0) + 1, orcollections.Counter. - What does
Countergive you over a plain dict? It counts an iterable in one call, returns 0 for missing keys instead ofKeyError, hasmost_common(k), and supports+and-between Counters. - Why is
s.count(ch)inside a loop slow? Eachcountwalks 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 aCounterand then making a second pass took a few milliseconds. - First non-repeating character? Pass 1:
counts = Counter(s). Pass 2: walksin order (withenumeratefor the index) and return the firstchwithcounts[ch] == 1; return-1(orNone) if there is none. O(n) time, O(1) extra space for a fixed alphabet. - 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, usemax(counts, key=counts.get). - What does
key=do inmax,minandsorted? 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". - How do you handle ties for the most frequent character? Find
top = max(counts.values()), then return every item whose count istop, sorted so the answer doesn't depend on the string's order.maxandmost_common(1)silently pick the first one seen. - What happens with
max()on an empty sequence?ValueError: max() iterable argument is empty. Check first (if not counts:) or passdefault=. - 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 withlower()andisalnum(). The best answer: clean, thenCounter(a) == Counter(b), O(n). Without Counter: a dict that counts up foraand down forb, 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 aCounter, then walk the string again in order and return the first character with count 1, in a few milliseconds. Return-1/Nonewhen 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 withValueError. 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.