Pattern-Based String Problems

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 5 Time to complete: ~25 minutes

Table of Contents

1. Anagram Check — Sorting Approach
2. Anagram Check — Counting Approach
3. Palindrome Check
4. Reverse Words in a Sentence
5. In-Place String Reversal via Two Pointers
6. Summary & Next Steps

1. Anagram Check — Sorting Approach

Two strings are anagrams if they contain exactly the same characters, possibly in a different order. The simplest approach: sort both and compare.

def is_anagram_sorting(a, b):
    return sorted(a) == sorted(b)
    # O(n log n) time — dominated by the sort
    # O(n) space — sorted() returns new lists

2. Anagram Check — Counting Approach

Sorting works but isn't the fastest option — counting character frequencies drops this to linear time (a preview of Module 8's hashing patterns):

def is_anagram_counting(a, b):
    if len(a) != len(b):
        return False
 
    counts = {}
    for char in a:
        counts[char] = counts.get(char, 0) + 1
    for char in b:
        if char not in counts:
            return False
        counts[char] -= 1
        if counts[char] == 0:
            del counts[char]
 
    return len(counts) == 0
    # O(n) time, O(1) space if the character set is bounded (e.g., lowercase letters)

This trades the sorting approach's O(n log n) for O(n) by using a hash map (dictionary) instead — the same time-for-space tradeoff introduced in Module 1, Chapter 6.

3. Palindrome Check

You saw the two-pointer version of this in Chapter 3 — here's the same idea applied specifically to strings, including normalization for real sentences:

def is_palindrome_sentence(text):
    cleaned = [char.lower() for char in text if char.isalnum()]
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1
    return True
    # O(n) time, O(n) space (for the cleaned list)
 
print(is_palindrome_sentence("A man, a plan, a canal: Panama"))   # True

4. Reverse Words in a Sentence

A common trap: reversing a sentence character-by-character reverses the letters within each word too. The fix is to reverse at the word level:

def reverse_words(sentence):
    words = sentence.split()          # O(n), splits on whitespace, drops extra spaces
    return " ".join(reversed(words))   # O(n)
    # O(n) time, O(n) space
 
print(reverse_words("the sky is blue"))     # "blue is sky the"

5. In-Place String Reversal via Two Pointers

Since Python strings are immutable (Chapter 5), true in-place reversal requires converting to a list first:

def reverse_in_place(chars):
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    # O(n) time, O(1) EXTRA space — mutates the list argument directly
 
word = list("hello")
reverse_in_place(word)
print("".join(word))        # "olleh"

Note the function takes a list of characters, not a str — this is exactly the "convert to a list, mutate, join back" pattern from Chapter 5, and it's the standard way "reverse a string in place" is asked and answered in interviews (since a raw Python str can never truly be reversed in place).

6. Summary & Next Steps

Key Takeaways

• Anagram checks can use sorting (O(n log n)) or character counting with a hash map (O(n)) — the counting approach previews Module 8's hashing patterns.
• Palindrome checks reuse the two-pointer pattern from Chapter 3, with a normalization step for real sentences (strip punctuation, lowercase).
• Reversing words vs. reversing characters are different operations — split into words first if word order (not letter order) is what needs reversing.
• True in-place string reversal requires converting to a list first, since Python strings can't be mutated directly.

Concept Check

1. Why does the counting approach to anagram checking beat the sorting approach on time complexity?
2. What mistake does "reverse the string" make if you don't split into words first?
3. Why is a list of characters used instead of a str when a problem explicitly asks for an in-place reversal?

Next Chapter

→ Chapter 7: Practice — Classic Array & String Problems

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index