Patterns

String problems

A string in an interview is usually an array of characters with a few extra rules: comparison, case, and whether order matters. If you can say which of those rules the prompt is using, the rest of the solution is a pattern you already know from arrays. This page does not try to cover parsing or Unicode edge cases in any serious way. It covers the two moves that show up constantly, with original examples, and it points at the neighboring pages when the move is really theirs.

Treat indexes the way you would in an array. A slice is contiguous. A bag of characters is not. The sliding window page is for contiguous slices with a running constraint. This page's anagram example is a bag: positions do not matter, only counts. Mixing those up produces code that happens to pass a short sample.

Bags of characters

Original task: you are given short labels. Group labels that use the same characters the same number of times, ignoring order. Case matters: A and a are different. Return the groups. The order of groups and the order inside a group do not matter.

A practical key is the string you get by sorting the characters. Labels that are anagrams share that key. A frequency tuple of 26 counts works too if you assume English letters. The sorted key does not assume an alphabet, which makes it the version to write unless the prompt restricts the alphabet and then asks you to optimize.

from collections import defaultdict


def group_labels(labels: list[str]) -> list[list[str]]:
    groups: dict[str, list[str]] = defaultdict(list)
    for label in labels:
        key = "".join(sorted(label))
        groups[key].append(label)
    return list(groups.values())


result = group_labels(["bat", "tab", "tap", "pat", "a"])
flat = {tuple(sorted(group)) for group in result}
assert flat == {("bat", "tab"), ("pat", "tap"), ("a",)}

For a label of length m, sorting the key costs O(m log m). Across all labels, if their total length is L and the longest label has length m, a safe bound is O(L log m). Building the dictionary is linear in the total length once the keys exist. Extra space is proportional to the total length, because you store every label again inside the groups. If the caller only needed the groups of indexes, you could store indexes and save the copies. The prompt here wants the labels.

Why the assert sorts each group: the function may return ["tab", "bat"] or ["bat", "tab"], and the groups themselves may come out in any order. Compare a set of sorted tuples, or sort everything before comparing. An assert that demands one exact nested list will fail on a correct solution and waste your time. That is a testing lesson, not a string lesson, and it belongs next to the common mistakes material too.

Empty labels are anagrams of each other. group_labels(["", ""]) should produce one group of two empty strings. A single character is a group of one. Labels with spaces: a space is a character, so "a b" and "ab" are not anagrams under this function. If the prompt says "ignore spaces and punctuation," filter them before you sort the key. Do the filter in one place. Doing it inside the comparison and not inside the key is how mismatches sneak in.

A frequency map from the arrays and hashing page is the other way to build the key: count each character, then use a tuple of counts. For a fixed alphabet that tuple hashes reliably. For arbitrary characters, the sorted string is less code. Mention both if the interviewer asks how you would speed up long labels over a small alphabet. Counting is linear in the label length, which beats sorting when m is large and the alphabet is small.

Palindromes and two pointers

A palindrome reads the same forward and backward. The array technique is two pointers moving inward, which the two pointers page justifies for sorted numeric pairs. Here the justification is symmetry, not a sum. The code is still "move the side that you are sure about."

Original task: return whether a phrase is a palindrome after ignoring characters that are not letters and after ignoring case. An empty phrase is a palindrome.

def phrase_is_palindrome(phrase: str) -> bool:
    left, right = 0, len(phrase) - 1
    while left < right:
        while left < right and not phrase[left].isalpha():
            left += 1
        while left < right and not phrase[right].isalpha():
            right -= 1
        if phrase[left].lower() != phrase[right].lower():
            return False
        left += 1
        right -= 1
    return True


assert phrase_is_palindrome("Top spot") is True
assert phrase_is_palindrome("Draw, ward") is True
assert phrase_is_palindrome("abc") is False
assert phrase_is_palindrome("") is True
assert phrase_is_palindrome(".,!") is True

Each pointer moves toward the center and never backward, so the scan is linear in the length of the phrase. Extra space is constant if you do not allocate a filtered copy. Building a cleaned string first is also linear time and linear space, and it is easier to debug. Under interview pressure, the cleaned string is a reasonable first version. Then mention the in-place scan as the tighter space bound. The time management advice applies: ship the version you can test.

isalpha treats letters from several alphabets as letters. That may be more than the prompt wanted. If the prompt says ASCII letters only, test 'a' <= ch.lower() <= 'z' after you decide how case works. Digits: this function ignores them because they are not letters. A prompt that says "alphanumeric" must use a different predicate. Read the word. A short phrase such as "Top spot" is enough to test the filter. You do not need a famous sentence, and you should not treat any sample as the problem statement. The function is the whole task.

The inner loops must also stop when left meets right. Otherwise a string of only punctuation walks off the end, or the two pointers cross and compare the wrong characters. The .,! assert is there to lock that down.

Stacks, windows, and the fork

Nesting questions, such as whether brackets match, are not bag questions and not palindrome questions. They belong to the stacks and queues page. Longest-substring questions that require contiguity belong to sliding windows. If you can delete characters from anywhere to form a palindrome, you are in a different, harder family, often edit distance, and you should not pretend the two-pointer scan solves it. The two-pointer scan answers a yes-or-no question about the phrase as it stands, after a simple filter.

A good interview sentence: "If order does not matter I will count characters. If the phrase has to mirror around its center I will move two pointers inward. If the answer has to be a contiguous slice with a constraint, I will use a window." Three sentences, three pages of this site. Practice saying them before you draw anything.

Practice drill

Implement group_labels and the palindrome check from a blank file. Add the empty-label assert and the punctuation assert. Then change the anagram task so case does not matter, and put the lower call in the key rather than in two places. Then write a tiny function that returns True when two labels are anagrams, using a single count map and no sort, and compare it with the sorted-key version on a list of pairs. They should agree. If they do not, the bug is almost always an alphabet assumption or a forgotten character class.

When that feels dull, you are ready to leave strings for a while. Dull means the fork between bag, mirror, and window has become automatic, which is what the four-week plan is hoping for by the end of the second week.