🎓 A1Learner
🔍
0 of 47 lessons completed

String Patterns in Interviews

A string pattern is a repeatable approach for solving a text problem. Many text problems reduce to counting letters, comparing letters, or scanning characters.

Spot the signal

A problem asks about same letters or same forward and backward reading. Sorting the letters exposes the signal.

first = "listen"
second = "silent"
print(sorted(first))
print(sorted(first) == sorted(second))

The template

Count the letters of a word into a hash map. The map is the template for most text checks.

def counts(text):
    result = {}
    for char in text:
        result[char] = result.get(char, 0) + 1
    return result
print(counts("banana"))

Worked problem: palindrome check

Two pointers walk in from both ends. The word is a palindrome when every pair matches.

word = "racecar"
left = 0
right = len(word) - 1
ok = True
while left < right:
    if word[left] != word[right]:
        ok = False
    left += 1
    right -= 1
print(ok)

Example

def counts(text):
    result = {}
    for char in text:
        result[char] = result.get(char, 0) + 1
    return result
print(counts("listen") == counts("silent"))
print(counts("hello") == counts("world"))

Key points

  • Palindrome: a word that reads the same forward and backward.
  • Anagram: two words that hold exactly the same letters.
  • Use a hash map of letter counts to compare two words.
  • Use two pointers from both ends to test a palindrome.
  • A string pattern restates a text problem as a small letter problem.

The code counts the letters of each word. Equal counts mean the words hold the same letters. The first pair matches, and the second pair does not.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Which problem signal points to counting letters?