Palindromes and anagrams in Python

Why it matters

Palindrome and anagram questions appear in a large share of beginner and intermediate string interviews. They look simple, which is the trap. An interviewer is not checking whether you can write a loop. They want to see whether you choose the right tool quickly: two pointers for a mirror check, a count of letters for a rearrangement check, and a dictionary keyed by a canonical form when you must group many words. Each of these tools shows up again in later modules, so the reasoning you practise here pays off across the course.

This lesson builds each solution from the idea up. You will see why a palindrome check can stop early, why the longest palindrome needs a different method, why counting letters beats sorting for anagrams, and how a dict turns "same letters" into a key you can look up.

The idea: mirrors and matching bags

A palindrome reads the same forwards and backwards. The words level, noon and racecar are palindromes. A phrase counts as a palindrome when you ignore capital letters, spaces and punctuation, so A man, a plan, a canal: Panama is one too.

Think of two people walking toward each other along a row of chairs, one starting from the left end and one from the right. Each time they reach a chair, they compare the letters they are standing next to. If the letters match, they both step inward. If any pair differs, the answer is no. If they meet in the middle without finding a mismatch, the answer is yes. That picture is the two pointers technique: two indexes that move toward each other.

An anagram is a rearrangement. listen and silent use the same letters, each the same number of times. Think of two bags of letter tiles. Empty the first bag onto a table, then check whether the second bag has exactly the same tiles. You do not need to rearrange the words to check it. You need to count the tiles.

These two pictures lead to the two main methods of this lesson, and a third method for grouping words with a dictionary.

Palindromes with two pointers

Here is the check for a phrase. It skips anything that is not a letter or digit, and it ignores case. The method str.isalnum() returns True for a letter or a digit.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True
 
line = input()
print("YES" if is_palindrome(line) else "NO")

Type this input when the program waits for it:

A man, a plan, a canal: Panama

The output is:

YES

Here is the trace in words. left starts at index 0, which is A. right starts at the last index, which is a. The two characters match when you ignore case, so both pointers move inward. The next pair is a space at left and an m at right. The inner while loop moves left past the space, so left lands on m. Now m and m match. The loop keeps going like this until the pointers meet in the middle at a of Panama. Every pair matched, so the function returns True.

Two details matter. First, the inner loops check left < right before they touch a character. Without that check, a phrase with only punctuation could push the pointers past each other and read outside the string. Second, the function stops at the first mismatch. It does not need to look at the rest of the text once it knows the answer.

The cost is O(n) time, because each pointer moves across the string at most once, and O(1) extra space, because the function stores only two integers.

Why not build a cleaned copy?

A common first attempt removes the punctuation into a new string, reverses that string and compares the two. In Python this is one line:

def is_palindrome_copy(s):
    clean = "".join(ch.lower() for ch in s if ch.isalnum())
    return clean == clean[::-1]

It is correct, and it is easy to explain. It also costs O(n) extra memory for the cleaned copy and the reversed copy. The two-pointer version gives the same answer in place. In an interview, describe the copy first, then say how the pointers remove the copies. That order shows you understand the trade-off rather than just knowing a trick.

Debugging a palindrome check

Suppose you wrote the check without the skipping loops, like this:

def is_palindrome_wrong(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
 
print(is_palindrome_wrong("racecar"))
print(is_palindrome_wrong("A man, a plan, a canal: Panama"))

The output is:

True
False

Test it on racecar, and it prints the right answer. Test it on A man, a plan, a canal: Panama, and it prints False. A beginner's first guess is that the code is wrong about palindromes. Debug it instead by following the characters.

1. The first character is A and the last is a. Their codes differ, because ord("A") is 65 and ord("a") is 97. The comparison != says they differ, so the function returns False.
2. The fix is to compare lowercase versions, which handles the case problem.
3. Fixing the case is not enough. After the A pair matches, the next pair is a space at the left and m at the right. The space is not a letter, so the comparison fails and the function returns False again.

Two separate bugs hide in one input: case and punctuation. The lesson's version handles both, and the rule to take away is that every comparison must match the problem's definition. When a palindrome check fails on a phrase, print the two characters being compared and their codes with print(repr(a), repr(b), ord(a), ord(b)). Two lines of debugging output usually show the problem in seconds.

Palindromes in the middle: the longest one

A harder question asks for the longest palindrome hidden inside a word. For babad the answer is bab (or aba, which has the same length). The two-pointer check does not help here, because you do not know where the palindrome starts.

The method that works is to expand around a centre. Every palindrome has a middle. For an odd-length palindrome such as aba, the middle is a single character, the b. For an even-length palindrome such as abba, the middle is the gap between the two bs. There are 2n - 1 possible centres in a string of length n: n single characters and n - 1 gaps.

From each centre, grow outward while the two letters on the sides match. Keep the largest palindrome found so far. The next program does that.

def expand(s, l, r):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return r - l - 1
 
def longest_palindrome(s):
    start, end = 0, 0
    for i in range(len(s)):
        length = max(expand(s, i, i), expand(s, i, i + 1))
        if length > end - start + 1:
            start = i - (length - 1) // 2
            end = i + length // 2
    return s[start:end + 1]
 
print(longest_palindrome("babad"))
print(longest_palindrome("cbbd"))
print(longest_palindrome("abba"))
print(longest_palindrome("abcbaxx"))
print(repr(longest_palindrome("")), longest_palindrome("a"), longest_palindrome("abc"))
print(expand("abcbaxx", 2, 2), expand("cbbd", 1, 2))

The output is:

bab
bb
abba
abcba
'' a a
5 2

Trace expand. It receives a left index and a right index. For the odd centre at index 1 (the a in babad, which is the centre of bab), it starts with l = 1 and r = 1. Both characters are a, so it moves to l = 0, r = 2. The characters are b and b, so it moves again, to l = -1, r = 3. Now l has run off the left end, so the loop stops. The length is r - l - 1, which is 3 - (-1) - 1 = 3. The palindrome starts at l + 1, index 0.

For an even centre, the call starts with r = l + 1. The string cbbd shows it. The centre between indexes 1 and 2 starts with l = 1 and r = 2, both b. It moves to l = 0, r = 3, where c and d differ, so the palindrome bb has length r - l - 1 = 3 - 0 - 1 = 2. The last line of the output shows the same two values.

Trace one more case, because it shows why the method stops where it does. Take abcbaxx, which has indexes 0 to 6. The odd centre at index 2 is the c. Start with l = 2 and r = 2, where both characters are c, so the palindrome is so far just c. Step outward to l = 1 and r = 3: both are b, so the palindrome is now bcb. Step again to l = 0 and r = 4: both are a, so the palindrome is abcba. Step again to l = -1 and r = 5. The left pointer has run off the start, so the while condition fails and the loop stops. The length is 5 - (-1) - 1 = 5, and the start is l + 1, which is 0.

The main function calls expand twice per index: once for the odd centre and once for the even centre. It converts the length back into a start and an end. The formulas start = i - (length - 1) // 2 and end = i + length // 2 find the edges of a palindrome of length length centred at i. The // operator is integer division, which rounds down. For these non-negative numbers it gives the same result as Java's integer division.

Time is O(n squared), because each of the 2n - 1 centres can grow up to n steps. The space is O(1). A method called Manacher's algorithm solves the same problem in O(n), but it is rarely expected in an interview, and the centre method is the one to explain clearly.

Palindrome with one deletion

A variation appears often in interviews: can you make the string a palindrome by deleting at most one character? For abca, deleting the c gives aba, which works. For abc, no single deletion helps. The idea is to run the two-pointer check. When the first mismatch appears, you have two choices: skip the left character, or skip the right one. Check both rest-of-string ranges with a plain palindrome test.

import sys
 
def is_pal_range(s, left, right):
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
 
def can_make_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return is_pal_range(s, left + 1, right) or is_pal_range(s, left, right - 1)
        left += 1
        right -= 1
    return True
 
for line in sys.stdin:
    print("YES" if can_make_palindrome(line.rstrip("\n")) else "NO")

Type these three lines in the input, one per line:

abca
abc
deeee

The output is:

YES
NO
YES

The program reads all the lines from standard input with for line in sys.stdin. This form stops at the end of the input, so you do not need to count the lines. The method rstrip("\n") removes the line break at the end of each line.

Trace abca, which has indexes 0 to 3. The first pair, index 0 (a) and index 3 (a), matches. The next pair, index 1 (b) and index 2 (c), differs. The function now tries two options. The first option skips the left letter and checks the range from index 2 to index 2, which is the single letter c, a palindrome. The second option skips the right letter and checks the range from index 1 to index 1, which is the single letter b, also a palindrome. One option is enough, so the answer is YES. Deleting b leaves aca, and deleting c leaves aba.

The two ranges are both needed because the deletion can happen on either side of the first mismatch. Deleting the left letter is the same as checking the range after it, and deleting the right letter is the same as checking the range before it.

The abc input has no single deletion that works, so both ranges fail. deeee works by deleting the first d, which leaves eeee. The function checks the range from index 1 to 4 and finds it is a palindrome.

The cost is O(n). The first mismatch triggers at most two extra passes over the string, and each pass is O(n).

Anagrams: counting letters

Two words are anagrams when they hold the same letters the same number of times. The simplest correct method sorts the characters of each word and compares the results, which costs O(n log n). The faster method counts letters.

Count the letters of the first word up, count the letters of the second word down, and check that every count ends at zero. If the words are anagrams, every letter that goes up is cancelled by a letter that goes down. A table makes this easy to follow. For listen and silent, the net count for each of the letters e, i, l, n, s and t is zero, because each letter is added once by listen and subtracted once by silent. A single extra letter in the second word would leave a count of -1 or +1, and the check would fail.

import sys
 
def is_anagram(a, b):
    if len(a) != len(b):
        return False
    count = [0] * 26
    for i in range(len(a)):
        count[ord(a[i]) - ord("a")] += 1
        count[ord(b[i]) - ord("a")] -= 1
    return all(c == 0 for c in count)
 
first = input()
second = input()
print(is_anagram(first, second))

Type these two lines in the input:

listen
silent

The output is:

True

The length check comes first. Two words of different lengths cannot be anagrams, so the function returns False at once, and the loop never runs. When the lengths match, the loop reads both words at the same index. count[ord(a[i]) - ord("a")] += 1 adds one for the letter from the first word, and the next line takes one away for the letter from the second word. The expression ord(letter) - ord("a") turns each lowercase letter into an index from 0 to 25, as you learned in the first lesson. The all(...) call checks that every count is zero.

Cost: O(n) time for the two words, and O(1) extra space for the 26 counters, because the list never grows. The sorting method costs O(n log n) time and O(n) extra space for the sorted copies. Mention both in an interview and explain why the count is better.

The standard library also has a short form. collections.Counter("listen") == collections.Counter("silent") gives True, because Counter builds the same letter counts for you. It is the right choice in production code. The explicit list shows the idea, and it makes the cost visible.

This version handles only lowercase letters a to z. Uppercase letters, digits and spaces produce an index that is not what you meant, and the next section shows what that failure looks like in Python.

Common mistakes with anagrams

Python lists accept negative indexes, so the bad indexes from uppercase letters do not always fail. Here is the case that fails silently:

print(is_anagram("L", "f"))

This prints True. The letter L has code 76, and 76 minus 97 (the code of a) is -21. Python reads -21 as "21 places from the end" of a list of 26 items, which is index 5, the same cell as f. The two letters cancel, so the function says the words are anagrams. A letter that is not in the list also produces an error when the index is too small, for example a space:

print(is_anagram("a b", "ba "))

This raises IndexError: list index out of range, because the space code 32 minus 97 is -65, which is outside the 26 cells. The fix is to lowercase the input first, with lower(), and to decide what to do with spaces and punctuation before you count. A safer choice is Counter, which accepts any character as a key and needs no fixed size.

Other mistakes are quieter. Skipping the length check gives a wrong answer: is_anagram("ab", "abc") returns True, because the loop never reads the extra c. If the second word is shorter, the loop raises IndexError. Comparing two lists with is checks whether they are the same object, not whether they hold the same numbers, so use ==.

Common mistakes with palindromes

The palindrome code is short, so its mistakes are about edge cases rather than long logic. These are the ones to check first.

• Forgetting case. Level is not a palindrome if you compare the raw characters, because L and l differ. Lowercase both characters before you compare, or lowercase the whole line first.
• Forgetting the punctuation rule. A phrase such as No lemon, no melon is a palindrome only when the comma and spaces are ignored. Decide what the problem says and write that rule into the loop.
• Missing even-length palindromes. A longest-palindrome function that expands only from single letters returns a for abba. The second call with i + 1 is what finds the even centre.
• Off-by-one in the loop. The loop condition is left < right, not left <= right. With <=, the loop also runs once when both pointers stand on the same middle letter. That comparison matches the letter with itself, so the answer stays correct.
• The empty string. len("") - 1 is -1, and s[-1] on an empty string raises IndexError. The while left < right loop never runs when right is -1, so the empty string is safe in the lesson's code. Test it anyway, because a change to the loop can break it.
• Building a cleaned copy when the pointers would do. The copy works, but it costs extra memory. Mention the two-pointer alternative when an interviewer asks about space.

Counting every palindrome

Sometimes the question is not for the longest palindrome but for how many palindromes a string contains. Every palindrome counts, even when it overlaps another one, and each single letter counts as a palindrome by itself. The string aaa contains six palindromic substrings: the three single letters, aa at positions 0 to 1, aa at positions 1 to 2, and aaa itself.

The expansion method counts them without any extra work. Every successful step of expand finds one more palindrome, because the letters on both sides match and the substring between them is a palindrome. The program adds one to a counter at each successful step.

import sys
 
def count_palindromes(s):
    count = 0
    for i in range(len(s)):
        for centre in range(2):
            l, r = i, i + centre
            while l >= 0 and r < len(s) and s[l] == s[r]:
                count += 1
                l -= 1
                r += 1
    return count
 
for line in sys.stdin:
    print(count_palindromes(line.rstrip("\n")))

Type these three lines in the input, one per line:

aaa
abc
abba

The output is:

6
3
6

Check abba by listing its palindromes: the four single letters, bb in the middle, and abba itself. That is 6. Check abc: it has three single letters and no longer palindrome, so 3. The loop uses centre as a switch: 0 means an odd centre, which starts with both pointers on the same index, and 1 means an even centre, which starts with the right pointer one step to the right. The same while loop serves both kinds of centre, which is why the code stays short.

The cost is O(n squared) in the worst case, because a string of all the same letter has about n squared / 2 palindromes, and the function visits each one. When an interviewer asks for the count, say that this method takes O(n squared), and that Manacher's algorithm can add up the same counts in O(n).

Sorting versus counting in practice

The sorting method and the counting method give the same answers, and each has a place. Sorting is easy to write and easy to explain: sorted(a) == sorted(b) is the whole check. Counting is faster on long words and uses less memory on very large inputs. The program below runs both methods on the same pairs of words and prints the two answers side by side.

import sys
 
def by_sorting(a, b):
    if len(a) != len(b):
        return False
    return sorted(a) == sorted(b)
 
def by_counting(a, b):
    if len(a) != len(b):
        return False
    count = [0] * 26
    for i in range(len(a)):
        count[ord(a[i]) - ord("a")] += 1
        count[ord(b[i]) - ord("a")] -= 1
    for c in count:
        if c != 0:
            return False
    return True
 
words = sys.stdin.read().split()
for i in range(0, len(words) - 1, 2):
    a, b = words[i], words[i + 1]
    print(f"{a} {b} -> sorting {by_sorting(a, b)}, counting {by_counting(a, b)}")

Type these five lines in the input:

listen silent
dusty study
rat car
aab aba
abc abcc

The output is:

listen silent -> sorting True, counting True
dusty study -> sorting True, counting True
rat car -> sorting False, counting False
aab aba -> sorting True, counting True
abc abcc -> sorting False, counting False

The two methods agree on every line. Notice the pair abc abcc: the lengths differ, so both methods return False at the first check, before any sorting or counting happens. That early exit is cheap and should always come first.

Checking that two methods agree on many inputs is a useful habit. It is called differential testing: you test a new method by comparing it with a simpler method you trust. When you write a fast version of an algorithm, keep the slow version in a test file and compare the two on many random inputs. The random module from the standard library makes the inputs. A mismatch shows you the exact input where the fast version is wrong.

Palindromes in numbers

Interviewers often ask whether a number is a palindrome, such as 121 or 1331, without turning it into a string. The method uses arithmetic instead. The last digit of a number is x % 10, and removing it is x // 10. Build the reversed number one digit at a time: multiply what you have by 10 and add the last digit.

def is_palindrome_number(x):
    if x < 0:
        return False
    original = x
    reversed_value = 0
    while x > 0:
        reversed_value = reversed_value * 10 + x % 10
        x = x // 10
    return original == reversed_value
 
print(is_palindrome_number(121), is_palindrome_number(120), is_palindrome_number(1331), is_palindrome_number(-121))

The output is:

True False True False

Trace 121. The first pass takes the last digit, 1, so reversed_value becomes 1, and x becomes 12. The second pass takes 2, so reversed_value becomes 12, and x becomes 1. The third pass takes 1, so reversed_value becomes 121, and x becomes 0. The loop stops, and 121 equals 121, so the answer is True. For 120 the reversed value is 21, which is not 120, so the answer is False. A negative number is never a palindrome in this definition, because its minus sign has no matching end.

In a language with fixed-size integers, reversing a very large number can overflow. Python integers have no fixed size, so the reversed number is always exact. The next lines show a number far larger than a 64-bit integer:

print(2 ** 100)
print(str(2 ** 100)[::-1])
print(is_palindrome_number(10 ** 40 + 1))

The output is:

1267650600228229401496703205376
6735023076941049228220060567621
True

The last line prints True, because 10 ** 40 + 1 is 1 followed by 39 zeros and a 1. The arithmetic version still works, but it takes time proportional to the number of digits. Interviewers may still ask for the half-reversal version, which reverses only half of the digits and so never builds a number bigger than the input. Mention the question of overflow when the problem uses a fixed-size type, because it shows you think about the limits of the types you use.

The method is O(d) time for a number with d digits and O(1) extra space. A string version, str(x) == str(x)[::-1], is O(d) time and O(d) space, which is also fine. Choose the arithmetic version when the problem says the input is a number, and the string version when it says the input is text.

A dict of keys: grouping anagrams

Sometimes you need to group many words, not just test two. Given the words eat tea tan ate nat bat, return the groups eat tea ate, tan nat and bat. The method is to build a key for each word: a value that is the same for all anagrams of the word. Sorting the letters gives a good key. eat, tea and ate all sort to aet.

A dict stores pairs of a key and a value. You give it a key and it finds the value fast, without searching the whole dict. Use the sorted letters as the key and a list of words as the value. Watch each word produce a key. Words with the same key land in the same list. At the end, each list is one group of anagrams.

The next program groups the words from one line. Python dict keeps the order in which keys were added, so the groups would print in the order the words appear. To make the output predictable and easy to compare, the program sorts the keys before it prints.

import sys
 
groups = {}
for w in sys.stdin.read().split():
    key = "".join(sorted(w))
    groups.setdefault(key, []).append(w)
 
for key in sorted(groups):
    print(" ".join(groups[key]))
print(sorted(groups))

Type this in the input:

eat tea tan ate nat bat

The output is:

bat
eat tea ate
tan nat
['abt', 'aet', 'ant']

The key for eat is aet, the letters of eat sorted. The key for tan is ant. The key for bat is abt. The keys are sorted before the loop, so the groups print in the order abt, aet, ant, which is why bat comes first. The last line shows the sorted keys themselves.

The line groups.setdefault(key, []).append(w) does two things in one step. If the key is not in the dict yet, setdefault inserts the empty list you passed in. Then append adds the word to that list. Without setdefault, you would write an if to check whether the key exists, create a list if it does not, and then add the word. The standard library's collections.defaultdict(list) does the same job with a shorter line.

The cost is O(n times m log m) for n words of length at most m, because each word is sorted once. The dict operations are cheap by comparison. A letter-count key avoids the sort. The next program builds a key from the 26 counts, such as a1e1t1:

def count_key(word):
    counts = [0] * 26
    for ch in word:
        counts[ord(ch) - ord("a")] += 1
    return "".join(f"{chr(ord('a') + i)}{c}" for i, c in enumerate(counts) if c > 0)
 
for w in ["eat", "tea", "ate", "tan", "nat", "bat"]:
    print(w, count_key(w))

The output is:

eat a1e1t1
tea a1e1t1
ate a1e1t1
tan a1n1t1
nat a1n1t1
bat a1b1t1

Both keys are correct. The sorted version is easier to explain.

What happens inside: keys and hashing

A dict finds a key by computing its hash, a number derived from the key's contents, and using that number to pick a slot. Two strings with the same characters have the same hash, which is why aet from eat and aet from tea land in the same slot. The dict then checks == to be sure the keys really match.

This is the reason immutability matters for keys. A string never changes, so its hash never changes, and the dict can always find it. A list has no hash at all, which is why d[["a"]] = 1 raises TypeError: cannot use 'list' as a dict key (unhashable type: 'list'). A tuple of letters is hashable, but the joined string is the simplest key to read and print. Use strings, numbers or tuples as keys.

Notice also that the key is built from the word, not the word itself. "".join(sorted(w)) makes a new string from the sorted letters. The original word eat is stored as the value in the list, so the output keeps the original spelling.

Variations and edge cases

Good solutions handle the inputs that look too small to matter.

• Empty and single-letter inputs. An empty string is a palindrome. A single letter is a palindrome. Two empty strings are anagrams of each other, because they have the same length and no letters.
• Case. The palindrome check ignores case in the code above. The anagram check does not, unless you lowercase first. Decide which rule the problem uses and write it down.
• Punctuation and spaces. For palindromes, the problem usually asks you to ignore them. For anagrams, a space is a character, so a b and ba are anagrams only if the spaces match too. Sorting handles any character without a fixed-size list, which is one reason to choose sorted or Counter when the input is not only lowercase letters.
• Odd and even lengths. The longest-palindrome function handles both. If you forget the even centre, abba returns a instead of abba.
• Ties. If two palindromes have the same length, the problem tells you which to return. The code above keeps the first one it finds, because a later palindrome of the same length does not replace it.
• Duplicates in groups. The grouping code keeps duplicate words in the same group, which is usually what you want. If the problem asks for unique words, use a set for each group.

Interview view: choosing the method

Interviewers like to see that you can name the tool before you write it. The table gives the answer for each question in this lesson.

When the answer is a long substring, explain that the O(n squared) method is the usual target, and mention Manacher's algorithm as the O(n) improvement. When the answer is a grouping, say what the key is and why every anagram shares it. Those two sentences cover most follow-up questions.

Practice

Try each exercise before you open the solution. The first few reuse the functions in this lesson directly. The later ones ask for a small change.

1. Check whether "Was it a car or a cat I saw" is a palindrome using the is_palindrome function. Predict the answer first.
2. Write is_palindrome_strict(s) that does not ignore case or punctuation. It should treat "Level" as not a palindrome.
3. Are "dusty" and "study" anagrams? Trace the count list after each step and show that every count ends at zero.
4. Modify is_anagram so it works for uppercase and lowercase letters as the same letter. Explain which change you made and why it is safe.
5. Write longest_palindrome_length(s) that returns only the length of the longest palindromic substring. Use the expansion method.
6. Write a function that returns the number of palindromic substrings in a string, such as 6 for "aaa" (three single letters, two aa and one aaa). Count every expansion step. Explain the complexity.
7. Group the words "eat tea tan ate nat bat" by the letter count instead of the sorted letters. Describe the key you build and check that it gives the same three groups.
8. Given a line of words, find the pair of anagrams with the most letters. Assume the words come in one line separated by spaces. What is the complexity of your method?
9. A colleague writes is_anagram with a dict that counts characters instead of a list. List one advantage and one disadvantage of the dict version, in terms of speed and memory.
10. Explain why expand(s, i, i) must be called for odd centres and expand(s, i, i + 1) for even centres, using the string "abba" as the example. What would the function return if you dropped the even calls?

Show the answer

1. The phrase reads wasitacaroracatisaw after removing spaces and punctuation, and lowercasing. That is a palindrome, so the program prints YES.
2. Use the two-pointer loop without the lower() calls and without the skipping loops: def is_palindrome_strict(s): l, r = 0, len(s) - 1; ... with if s[l] != s[r]: return False. "Level" fails because L and l differ.
3. Count d, u, s, t, y for dusty, adding one for each letter, giving 1 in each. Subtract for study: s, t, u, d, y, each minus one, so every count returns to 0. The words are anagrams.
4. Call lower() on both strings before the loop. The change is safe for this problem because the rule says case does not matter. If you wanted case to matter, you would leave the code alone.
5. Compute expand for both centres at each index as in the lesson, keep the largest length, and return it. For babad the answer is 3.
6. Each centre counts every palindrome it reaches, starting with the centre itself. For aaa the three odd centres find a, a and a, plus aaa from the middle centre, which is 4. The two even centres find aa each, which is 2. The total is 6. Each of the 2n - 1 centres can expand up to n steps, so the time is O(n squared).
7. The key is the letters that occur, each followed by its count, in alphabetical order. For eat the key is a1e1t1. tea and ate give the same key, tan and nat give a1n1t1, and bat gives a1b1t1. The three groups are the same as with sorted letters.
8. Group the words with a dict keyed by the sorted letters, as in the lesson. Every group with two or more words holds anagrams of the same length. Among the groups with two or more words, keep the one whose words are longest, and print its first two words. Time is O(n m log m), and the sorting cost dominates.
9. The dict version works for any characters, including Unicode, without choosing a list size. The disadvantage is speed and memory: each lookup hashes the key and the dict uses more memory per entry than a fixed list of 26 integers.
10. An odd palindrome has its centre on a letter, so expand(s, i, i) starts with both pointers at i. An even palindrome has its centre in a gap, so expand(s, i, i + 1) starts with the two pointers on neighbouring letters. For "abba", the even centre between indexes 1 and 2 gives the answer abba. Without the even calls the function cannot find abba. With odd centres alone, every palindrome it finds has length 1, and it keeps the first letter, a, as the answer.

What you now know

• A palindrome check uses two pointers moving inward. Skip non-letters, compare lowercase characters, and stop at the first mismatch. Time O(n), space O(1).
• The longest palindrome expands around 2n - 1 centres, odd and even. Time O(n squared), space O(1).
• A palindrome after one deletion tries two shorter palindrome checks at the first mismatch.
• Anagrams use a count of 26 letters: add for the first word, subtract for the second, and check for zeros. Time O(n), space O(1). sorted(a) == sorted(b) is the short version.
• Python lists accept negative indexes, so a bad letter can point at the wrong cell without an error. Lowercase the input first.
• A dict keyed by a canonical form, such as the sorted letters, groups all anagrams under one key. Use setdefault to create each group the first time you need it.

The next lesson combines these ideas with compression and sliding windows, which are the other two patterns interviewers expect you to know.