These are the notes for Python Coding Questions, episode 11, the first round of string questions. A string (str) is a piece of text: a sequence of characters such as "SyntaxPilot". Three classic questions: reversing a string (and why Python has no .reverse() for it), checking a palindrome while ignoring capitals and punctuation, and counting vowels, where a condition that reads like perfect English turns out to be true for every single letter. Along the way you'll see why strings are immutable, what a lazy iterator is, how a slice with a negative step walks backwards, and how two pointers check a palindrome without making a copy.
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real. Two things will differ on your machine: memory addresses like 0x7f5335246a40 (and the numbers id() prints) change on every run, and tracebacks show the full path to your file; here it is shortened to main.py.
Q1: Reverse a string
Real-life example: the front of an ambulance says ECNALUBMA: the word, written backwards. Up close it looks wrong, but the driver ahead sees it in the mirror, the right way round: AMBULANCE. Reversing a string means the same thing: give back its letters from last to first.
| Input | Output |
|---|---|
"SyntaxPilot" |
"toliPxatnyS" |
"chai" |
"iahc" |
"a" (one letter) |
"a" |
"" (empty) |
"" |
Ask the interviewer: should I return a new string or print it? Can I use slicing and reversed(), or do you want a loop? (Often they first accept s[::-1], then say "now without it".) What about the empty string?
Attempt 1: name.reverse()
Lists have a reverse() method, so let's try it on a string.
name = "SyntaxPilot"
name.reverse()
print(name)
Output:
Traceback (most recent call last):
File "main.py", line 2, in <module>
name.reverse()
^^^^^^^^^^^^
AttributeError: 'str' object has no attribute 'reverse'
Why it fails: an attribute is anything you reach with a dot: a method like .upper() or a value. An AttributeError means "this kind of object has nothing with that name". str simply has no reverse method. Only list does.
Attempt 2: reversed(), and changing one letter
Next idea: the built-in reversed() function. And, while we're at it, try changing the first letter directly.
name = "SyntaxPilot"
print(reversed(name))
name[0] = "s"
Output (the address after at changes on every run):
<reversed object at 0x7f5335246a40>
Traceback (most recent call last):
File "main.py", line 3, in <module>
name[0] = "s"
~~~~^^^
TypeError: 'str' object does not support item assignment
Two surprises:
reversed(name)is not a string. It's areversedobject: an iterator, something that hands out items one at a time when asked. It is lazy: it doesn't do the work up front; it gives the next letter only when someone asks for it. Printing it shows only its type and its memory address.name[0] = "s"is refused. Item assignment means putting a new value into one position withx[i] = .... Strings don't allow it.
Here is the lazy iterator in action. next(it) asks for one more item; list(it) asks for all the rest:
name = "SyntaxPilot"
it = reversed(name)
print(next(it), next(it), next(it)) # one letter at a time, on request
print(list(it)) # the rest
print(list(it)) # used up: nothing left
Output:
t o l
['i', 'P', 'x', 'a', 't', 'n', 'y', 'S']
[]
An iterator is used up after one pass: the second list(it) is empty. So reversed() gives you the letters, but you still have to glue them back into a string.
Why: strings are immutable
Immutable means: once the object is made, it can never change. A Python string is immutable. That is why both attempts failed: list.reverse() flips a list in place (changes that same list; lists are mutable), and you can't change a string in place. Every "reverse" for a string must build a new string.
name = "chai"
print(id(name))
name = name[::-1] # a NEW string; the name now points to it
print(name, id(name))
Output (the id numbers differ on every run):
140282771908832
iahc 140282771909648
id() gives a number that identifies an object while it exists. The two numbers differ: name = name[::-1] did not change the old string; it made a new one and moved the name (the variable) to point at it. Methods that seem to change a string, like s.upper() or s.replace(...), also return a new string and leave s as it was. To "change" the first letter, build a new string: "s" + name[1:].
The fix: a slice with step −1, or join(reversed(s))
A slice takes part of a sequence: s[start:stop:step]. start is where to begin, stop is where to end (not included), and step is how far to jump each time (default 1). The step can be negative: then Python walks backwards. Leave out start and stop and use step −1: s[::-1] starts at the last letter and walks to the first.
The other way: take the reversed() iterator and join its letters. "".join(items) glues a sequence of strings together, with the string before the dot (here the empty string "") as the glue between them.
name = "SyntaxPilot"
print(name[::-1]) # start to end, step -1
print("".join(reversed(name))) # join the letters back into one string
print(name[::2], name[-3:], name[::-2])
print(""[::-1] == "", "a"[::-1])
Output:
toliPxatnyS
toliPxatnyS
SnaPlt lot tlPanS
True a
name[::-1]and"".join(reversed(name))give the same answer.name[::2]: every second letter from the front: S, n, a, P, l, t.name[-3:]: a negative index counts from the end (−1 is the last letter), so this is "from the third-last letter to the end":lot.name[::-2]: backwards, skipping one each time.- Edge cases: the empty string reversed is still empty, and one letter is itself.
Walking through the indexes
Every character has two positions: a normal index from the front, and a negative one from the back.
| Character | S | y | n | t | a | x | P | i | l | o | t |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Negative index | −11 | −10 | −9 | −8 | −7 | −6 | −5 | −4 | −3 | −2 | −1 |
With a negative step and no start, the slice starts at index 10 (−1) and goes 10, 9, 8, ... 0. Slices never crash on bad positions; they just give what fits:
s = "SyntaxPilot"
print(repr(s[100:]), repr(s[5:2]), repr(s[5:2:-1]), repr(s[-100:3]))
Output:
'' '' 'xat' 'Syn'
repr() shows a value the way you'd type it in code, with quotes, so an empty string is visible as ''. s[5:2] is empty (you can't walk forwards from 5 to 2), but s[5:2:-1] walks backwards: indexes 5, 4, 3, which are x, a, t. (Unlike s[100], which would raise IndexError, a slice past the end is just empty.)
The follow-up: no slicing, no reversed()
Interviewers often say: "Fine. Now show me the loop." Walk the indexes from the last one down to 0, collect the letters in a list, and join once at the end.
def reverse(s):
letters = []
for i in range(len(s) - 1, -1, -1): # last index down to 0
letters.append(s[i])
return "".join(letters) # one new string at the end
print(reverse("SyntaxPilot"), reverse("chai"), repr(reverse("")))
print(reverse("namaste") == "namaste"[::-1])
Output:
toliPxatnyS iahc ''
True
range(len(s) - 1, -1, -1) means: start at the last index, stop before −1 (so 0 is the last one used), step −1. For the empty string, range(-1, -1, -1) is empty, the loop never runs, and "".join([]) is "".
Step by step for "chai":
def reverse(s):
letters = []
for i in range(len(s) - 1, -1, -1):
letters.append(s[i])
print(f"i={i} s[i]={s[i]!r} letters={letters}")
return "".join(letters)
print(reverse("chai"))
Output:
i=3 s[i]='i' letters=['i']
i=2 s[i]='a' letters=['i', 'a']
i=1 s[i]='h' letters=['i', 'a', 'h']
i=0 s[i]='c' letters=['i', 'a', 'h', 'c']
iahc
The last letter goes in first; after i = 0 the range stops (it never reaches −1), and one join makes the answer.
Why a list and one join, and not result = result + s[i]? Because strings are immutable, each + builds a brand-new string and copies everything so far. For a long string that copying adds up to O(n²) in the worst case. Appending to a list is O(1), and one join at the end is O(n). (Episode 15 times the difference.)
- Every version is O(n) time (each letter is read once) and O(n) space (a new string of the same length; it has to exist, because it's the answer).
Q2: Palindrome, ignoring case and punctuation
Real-life example: Malayalam, the language spoken in Kerala, reads the same from either end. That's a palindrome: a word or sentence that reads the same forwards and backwards. Sentences can be palindromes too: "Never odd or even" is the same letters both ways once you ignore the spaces, and "Was it a car or a cat I saw?" once you also ignore the capitals and the question mark. The question says: only letters and digits count.
| Input | Output |
|---|---|
"madam" |
True |
"Malayalam" |
True (capital M = small m) |
"Never odd or even" |
True (spaces ignored) |
"Was it a car or a cat I saw?" |
True |
"No 'x' in Nixon" |
True |
"hello" |
False |
"" |
True (nothing differs) |
"12321" |
True (digits count) |
Ask the interviewer: does case matter? Do spaces and punctuation count? Are digits included? What should an empty string, or a string of only punctuation, return?
Attempt: compare with the reverse
With the slice we just learned: a string is a palindrome if it equals its reverse.
def is_palindrome(s):
return s == s[::-1]
for s in ["madam", "Malayalam", "Never odd or even"]:
print(s, "->", is_palindrome(s))
Output:
madam -> True
Malayalam -> False
Never odd or even -> False
Why it's wrong: look at what the reverses really are:
for s in ["Malayalam", "Never odd or even"]:
print(repr(s), "reversed:", repr(s[::-1]))
print("M" == "m", ord("M"), ord("m"))
Output:
'Malayalam' reversed: 'malayalaM'
'Never odd or even' reversed: 'neve ro ddo reveN'
False 77 109
To Python, "M" and "m" are different characters. ord() gives a character's number code: 77 for M, 109 for m. Comparing strings compares those codes, so "Malayalam" and "malayalaM" differ in the first letter. In the sentence, the spaces land in different places when reversed. The code is fine for madam; it just answers a different question from the one asked.
The fix: clean first, then compare
Two string methods do the cleaning:
ch.isalnum(): True ifchis alphanumeric, meaning a letter or a digit. False for spaces and punctuation.ch.lower(): returns the lowercase version, so"M"becomes"m". Characters with no lowercase form (digits, punctuation) come back unchanged.
for ch in "Ab3 ?,_é":
print(repr(ch), ch.isalnum(), ch.lower())
s = "Was it a car or a cat I saw?"
clean = "".join(ch.lower() for ch in s if ch.isalnum())
print(clean)
print(clean[::-1])
Output:
'A' True a
'b' True b
'3' True 3
' ' False
'?' False ?
',' False ,
'_' False _
'é' True é
wasitacaroracatisaw
wasitacaroracatisaw
Note _ (underscore) is not alphanumeric, while é is (it's a letter, just not an English one). The expression inside join(...) is a generator expression: like a list comprehension, ch.lower() for ch in s if ch.isalnum() produces each lowered letter or digit, but one at a time, without building a list first.
def is_palindrome(s):
clean = "".join(ch.lower() for ch in s if ch.isalnum()) # letters, digits
return clean == clean[::-1]
for s in ["madam", "Malayalam", "Never odd or even",
"Was it a car or a cat I saw?", "No 'x' in Nixon", "hello", "", "12321"]:
print(repr(s), "->", is_palindrome(s))
Output:
'madam' -> True
'Malayalam' -> True
'Never odd or even' -> True
'Was it a car or a cat I saw?' -> True
"No 'x' in Nixon" -> True
'hello' -> False
'' -> True
'12321' -> True
Every test is right. (repr uses double quotes for "No 'x' in Nixon" because the string contains single quotes.) The empty string is True: "" == "", there's nothing that differs.
- O(n) time (one pass to clean, one to reverse, one to compare) and O(n) extra space, because we built the cleaned copy and its reverse.
The follow-up: two pointers, O(1) extra space
"Can you do it without the copy?" Yes: two pointers, one index i from the front and one j from the back (the pattern from episode 6). While they haven't met: skip anything that isn't a letter or digit, on either side; if the two lowered characters differ, it's not a palindrome; otherwise move both inwards.
def is_palindrome(s):
i, j = 0, len(s) - 1
while i < j:
if not s[i].isalnum():
i += 1 # skip punctuation on the left
elif not s[j].isalnum():
j -= 1 # ...and on the right
elif s[i].lower() != s[j].lower():
return False
else:
i += 1
j -= 1
return True
for s in ["Malayalam", "Never odd or even",
"Was it a car or a cat I saw?", "hello", "", "?!"]:
print(repr(s), "->", is_palindrome(s))
Output:
'Malayalam' -> True
'Never odd or even' -> True
'Was it a car or a cat I saw?' -> True
'hello' -> False
'' -> True
'?!' -> True
The same answers, and "?!" (only punctuation) is True: after skipping, there's nothing left to compare. For "", j starts at −1, i < j is false straight away, and the answer is True.
The pointers step by step
"No 'x' in Nixon", with a print in each branch:
def is_palindrome(s):
i, j = 0, len(s) - 1
while i < j:
if not s[i].isalnum():
print(f"i={i} {s[i]!r} skip left")
i += 1
elif not s[j].isalnum():
print(f"j={j} {s[j]!r} skip right")
j -= 1
elif s[i].lower() != s[j].lower():
print(f"i={i} {s[i]!r} vs j={j} {s[j]!r} differ")
return False
else:
print(f"i={i} {s[i]!r} vs j={j} {s[j]!r} match")
i += 1
j -= 1
return True
print(is_palindrome("No 'x' in Nixon"))
Output:
i=0 'N' vs j=14 'n' match
i=1 'o' vs j=13 'o' match
i=2 ' ' skip left
i=3 "'" skip left
i=4 'x' vs j=12 'x' match
i=5 "'" skip left
i=6 ' ' skip left
i=7 'i' vs j=11 'i' match
i=8 'n' vs j=10 'N' match
True
| Step | i, s[i] | j, s[j] | Action |
|---|---|---|---|
| 1 | 0, N |
14, n |
n == n: move both |
| 2 | 1, o |
13, o |
match: move both |
| 3-4 | 2, space; 3, ' |
12 | not alphanumeric: i skips |
| 5 | 4, x |
12, x |
match: move both |
| 6-7 | 5, '; 6, space |
11 | i skips |
| 8 | 7, i |
11, i |
match |
| 9 | 8, n |
10, N |
match; now i = 9, j = 9: the pointers met |
Each step moves at least one pointer one place inwards, so every character is visited at most once: O(n) time. The only extra memory is two numbers: O(1) extra space. That's the answer interviewers hope for.
Q3: Count vowels
Real-life example: a school word game. The teacher writes a word and you count the vowels: a, e, i, o and u. Chai has two: a and i. When she writes INDIA in capitals, it still has three vowels. Keep that in mind.
| Input | Output |
|---|---|
"Chai" |
2 |
"rhythm" |
0 (y is not a vowel here) |
"INDIA" |
3 (capitals count) |
"Good morning, Asha!" |
6 |
"" |
0 |
Ask the interviewer: do capitals count? Is y a vowel? (Usually no.) Should I also report how many of each vowel?
Attempt 1: reading the English straight into code
def count_vowels(s):
count = 0
for ch in s:
if ch == "a" or "e" or "i" or "o" or "u":
count += 1
return count
print(count_vowels("Chai"))
print(count_vowels("rhythm"))
Output:
4
6
Why it's wrong: four for Chai, and six for rhythm, which has no vowels at all. Every single letter was counted. No error, just a wrong answer.
or does not share the ch == part. Python reads the condition as (ch == "a") or "e" or "i" or .... And in an if, every value is either truthy (counts as True) or falsy (counts as False). A non-empty string is truthy; only the empty string "" is falsy (as are 0, None and empty collections).
print(bool("e"), bool(""), bool(0), bool(" "))
ch = "C"
print(ch == "a" or "e" or "i") # what the condition really is
print((ch == "a") or "e") # the same thing, with brackets
print(ch == "a" or ch == "e" or ch == "i") # the long but correct form
Output:
True False False True
e
e
False
or returns the first truthy value it finds (or the last value if none is truthy). For "C", ch == "a" is False, so or moves on and returns "e", which is truthy, so the if always runs. Even a single space " " is truthy. The long form, repeating ch == each time, is correct but clumsy.
Attempt 2: ch in "aeiou"
The fix that reads well: ch in "aeiou". For strings, in checks whether one string appears inside another.
def count_vowels(s):
count = 0
for ch in s:
if ch in "aeiou":
count += 1
return count
print(count_vowels("Chai"), count_vowels("rhythm"), count_vowels("INDIA"))
Output:
2 0 0
Chai 2 and rhythm 0: both right. But INDIA: 0. Capital "A" is not in the string of small vowels: the same trap as Malayalam. The string must be lowered first.
The fix: lower(), a set, and sum
from collections import Counter
VOWELS = set("aeiou")
def count_vowels(s):
return sum(1 for ch in s.lower() if ch in VOWELS)
for s in ["Chai", "rhythm", "INDIA", "Good morning, Asha!", ""]:
print(repr(s), count_vowels(s))
print(Counter(ch for ch in "Good morning, Asha!".lower() if ch in VOWELS))
Output:
'Chai' 2
'rhythm' 0
'INDIA' 3
'Good morning, Asha!' 6
'' 0
Counter({'o': 3, 'a': 2, 'i': 1})
s.lower()makesINDIAintoindia, so capitals count.- A set is a collection of unique items with fast lookup:
ch in VOWELSis a hash lookup, O(1) on average.set("aeiou")makes a set of the five letters. sum(1 for ch in ... if ...)is a generator expression that produces a1for every vowel, andsumadds them up: a count in one line.Counter(from thecollectionsmodule) is a dictionary that counts things: each vowel maps to how many times it appeared.
Step by step for "Good morning, Asha!", here is what each piece holds:
from collections import Counter
VOWELS = set("aeiou")
s = "Good morning, Asha!"
print(s.lower())
print([ch for ch in s.lower() if ch in VOWELS])
c = Counter(ch for ch in s.lower() if ch in VOWELS)
print(c, sum(c.values()), c["o"], c["u"])
print("ae" in "aeiou", "ae" in VOWELS)
Output:
good morning, asha!
['o', 'o', 'o', 'i', 'a', 'a']
Counter({'o': 3, 'a': 2, 'i': 1}) 6 3 0
True False
The capital A of Asha became a and was counted. sum(c.values()) gives the total 6. c["u"] is 0: a Counter returns 0 for a missing key instead of raising KeyError.
Set or string? With only five vowels, ch in "aeiou" is just as fast in practice. But in on a string checks for a substring (a piece of the string), so "ae" in "aeiou" is True. A set checks for one whole item, which is what you mean: "is this one character a vowel?" Here ch is always one character, so both work; the set says what you mean.
- O(n) time (one pass over the string;
lower()is another pass, still O(n)) and O(1) extra space for the set (always five items). Strictly,s.lower()builds a lowered copy, which is O(n); lowering each character inside the loop,ch.lower() in VOWELS, avoids even that.
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
name.reverse() |
AttributeError: 'str' object has no attribute 'reverse' |
only lists have .reverse(); strings can't change |
name[::-1] |
print(reversed(name)) |
<reversed object at 0x7f...> (address varies) |
a lazy iterator, not a string | "".join(reversed(name)) |
name[0] = "s" |
TypeError: 'str' object does not support item assignment |
strings are immutable | build a new string: "s" + name[1:] |
result = result + ch in a loop |
correct, but slow on long strings | each + copies the whole string |
append to a list, join once |
s == s[::-1] on a sentence |
Malayalam -> False |
'M' != 'm', spaces and punctuation count |
lower() and isalnum() first |
ch == "a" or "e" or ... |
rhythm → 6, every letter counted |
"e" alone is truthy |
ch in "aeiou" |
ch in "aeiou" without lowering |
INDIA → 0 |
'A' is not in "aeiou" |
s.lower() first |
| counting consonants as "not a vowel" | spaces and punctuation counted | " " is not a vowel either |
also check ch.isalpha() |
s.split(" ") on extra spaces |
['', '', 'chai', '', '', 'is', ...] |
splits on every single space | s.split() |
Your turn: reverse the words in a sentence (solution)
Reverse the order of the words, not the letters. " chai is hot " becomes "hot is chai", and the extra spaces disappear.
Solution
s.split() with no argument splits on any run of whitespace and drops empty pieces. s.split(" ") splits on every single space, so extra spaces become empty strings ''. Watch the difference:
s = " chai is hot "
print(s.split())
print(s.split(" "))
print(repr(" ".join(s.split(" ")[::-1])))
print(repr(" ".join(s.split()[::-1])))
Output:
['chai', 'is', 'hot']
['', '', 'chai', '', '', 'is', '', 'hot', '']
' hot is chai '
'hot is chai'
With split(" "), the empty pieces are reversed too, and joining them back brings the extra spaces back (in mirrored places). With split(), you get the clean answer. The full solution, with edge cases:
def reverse_words(s):
return " ".join(reversed(s.split()))
for s in [" chai is hot ", "chai is hot", "hello", " ", ""]:
print(repr(s), "->", repr(reverse_words(s)))
Output:
' chai is hot ' -> 'hot is chai'
'chai is hot' -> 'hot is chai'
'hello' -> 'hello'
' ' -> ''
'' -> ''
reversed() works here because join accepts any iterable (anything you can loop over), so there's no need to build a reversed list first; s.split()[::-1] works too. O(n) time and O(n) space for the list of words and the new string.
Practice questions (with solutions)
1. Reverse the words without split() or join on the sentence. The interviewer's follow-up to "your turn": " chai is hot " → "hot is chai", collecting words by hand.
Solution
Walk the characters. Letters go into the current word; a space ends a word (if there is one). Then walk the list of words from the last one down to 0, exactly like the loop reverse in Q1.
def reverse_words_manual(s):
words, word = [], []
for ch in s:
if ch == " ":
if word: # a word just ended
words.append("".join(word))
word = []
else:
word.append(ch)
if word: # the last word
words.append("".join(word))
out = []
for i in range(len(words) - 1, -1, -1):
out.append(words[i])
return " ".join(out)
for s in [" chai is hot ", "chai is hot", "hello", " ", ""]:
print(repr(s), "->", repr(reverse_words_manual(s)))
Output:
' chai is hot ' -> 'hot is chai'
'chai is hot' -> 'hot is chai'
'hello' -> 'hello'
' ' -> ''
'' -> ''
The if word: check (an empty list is falsy) is what drops the extra spaces. Don't forget the last word: the sentence may not end with a space. O(n) time, O(n) space.
2. Longest palindrome word in a sentence. "Madam Anna saw a racecar at noon" → "racecar". Ignore case and punctuation inside each word.
Solution
Split into words, clean each word like Q2, and keep the longest one that equals its reverse. Using > (not >=) keeps the first one on a tie.
def longest_palindrome_word(sentence):
best = ""
for word in sentence.split():
clean = "".join(ch.lower() for ch in word if ch.isalnum())
if clean == clean[::-1] and len(clean) > len(best):
best = clean
return best
print(longest_palindrome_word("Madam Anna saw a racecar at noon"))
print(longest_palindrome_word("Wow, level: Malayalam!"))
print(repr(longest_palindrome_word("hello world")))
print(repr(longest_palindrome_word("")))
Output:
racecar
malayalam
''
''
madam (5), anna (4), a (1), racecar (7) and noon (4) are all palindromes; racecar is the longest. The comma and colon are cleaned away, so "Wow," is just wow. With no palindrome words, the answer is "". O(n) time overall (each character is cleaned and compared a constant number of times), O(n) space for the words. Ask whether single letters like a should count; here they do.
3. Count consonants (letters that aren't vowels). "Good morning, Asha!" → 9.
Solution
The trap: "not a vowel" is not the same as "a consonant". Spaces, commas and ! aren't vowels either. Add ch.isalpha() (True only for letters, not digits) to the check.
VOWELS = set("aeiou")
def count_consonants(s):
return sum(1 for ch in s.lower() if ch.isalpha() and ch not in VOWELS)
def count_consonants_wrong(s):
return sum(1 for ch in s.lower() if ch not in VOWELS)
for s in ["Chai", "rhythm", "INDIA", "Good morning, Asha!", ""]:
print(repr(s), count_consonants(s), count_consonants_wrong(s))
Output:
'Chai' 2 2
'rhythm' 6 6
'INDIA' 2 2
'Good morning, Asha!' 9 13
'' 0 0
For single words both versions agree, which is how the bug hides. On the sentence, the wrong version counts the two spaces, the comma and the !: 13 instead of 9. Test with a sentence! O(n) time, O(1) extra space.
4. Palindrome after removing at most one letter. "abca" → True (remove c or b), "raceacar" → True (remove an a), "abc" → False.
Solution
Brute force: try removing each letter in turn (t = s[:k] + s[k + 1:]) and check whether t == t[::-1]. Each check is O(n) and there are n letters: O(n²) time, and a new string every time.
Two pointers: move inwards as in Q2. At the first mismatch, one of the two letters must go: either skip the left one (check i+1..j) or skip the right one (check i..j-1). If either remaining range is a palindrome, the answer is True. There is only one mismatch to "spend", so no further skipping is allowed.
def is_pal_range(s, i, j):
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
def almost_palindrome(s):
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
# one mismatch allowed: drop the left letter OR the right one
return is_pal_range(s, i + 1, j) or is_pal_range(s, i, j - 1)
i += 1
j -= 1
return True
for s in ["abca", "racecar", "raceacar", "abc", "deeee", "ab", ""]:
print(repr(s), "->", almost_palindrome(s))
Output:
'abca' -> True
'racecar' -> True
'raceacar' -> True
'abc' -> False
'deeee' -> True
'ab' -> True
'' -> True
For "abca": a == a, then b vs c differ; dropping b leaves "c" (a palindrome). For "deeee", d vs e differ at once, and dropping d leaves "eeee". O(n) time (at most two extra passes), O(1) extra space, and no new strings are built.
Quick quiz
What does this print?
s = "Python"
print(s[::-2], s[-1::-3])
(A) nhy th (B) nhy nt (C) Pto nh (D) nohtyP P
Answer
(B). The indexes of Python are P 0, y 1, t 2, h 3, o 4, n 5.
s[::-2]starts at the last letter,n(index 5), and steps back two at a time: indexes 5, 3, 1, which aren,h,y.s[-1::-3]also starts atn(index −1 is index 5) and steps back three: indexes 5, 2, which aren,t. The next would be −1, which is past the start, so it stops.
nhy nt
You can check the indexes with range: list(range(5, -1, -2)) is [5, 3, 1] and list(range(5, -1, -3)) is [5, 2].
Interview questions
- How do you reverse a string in Python?
s[::-1], a slice with step −1. Or"".join(reversed(s)). Both O(n) time and O(n) space. - Why is there no
str.reverse()? Strings are immutable: they can't change in place.list.reverse()flips a list in place, which is impossible for a string; every reverse must return a new string. - What does
reversed(s)return? Areversedobject: a lazy iterator that yields the characters from last to first, one at a time, and is used up after one pass. Join it, or pass it tolist(), to get the result. - Reverse a string without slicing or
reversed()? Loopifromlen(s) - 1down to 0, appends[i]to a list, and"".jointhe list once. Avoidresult += chin a loop: each+copies the whole string. - Check a palindrome ignoring case and punctuation? Keep
ch.lower()for everychwherech.isalnum(), join, and compare with its reverse: O(n) time, O(n) space. Or two pointers from both ends, skipping non-alphanumeric characters and comparing lowered characters: O(n) time, O(1) extra space. - Why is
if ch == "a" or "e":always true? It means(ch == "a") or "e", and the non-empty string"e"is truthy. Writech in "aeiou"(orch == "a" or ch == "e"). - Count vowels, including capitals?
sum(1 for ch in s.lower() if ch in set("aeiou")), or aCounterfor each vowel's count. O(n) time. split()vssplit(" ")?split()splits on any run of whitespace and drops empty pieces;split(" ")splits on every single space, so extra spaces give empty strings.
Glossary
| Term | Meaning | Example |
|---|---|---|
String (str) |
A sequence of characters: text | "SyntaxPilot" |
| Character | One letter, digit, space or symbol in a string | s[0] → 'S' |
| Index | A position in a string, from 0 | s[3] |
| Negative index | A position counted from the end; −1 is the last | s[-1] → 't' |
| Immutable | Can never change after it's made | strings, so no s[0] = "x" |
| Mutable | Can be changed in place | lists: letters.reverse() |
| In place | Changing the same object, not making a new one | list.reverse() |
| Attribute | Anything reached with a dot: a method or value | s.upper |
AttributeError |
The object has no attribute with that name | 'str' object has no attribute 'reverse' |
| Item assignment | Putting a value at one position, x[i] = v |
name[0] = "s" |
TypeError |
An operation the type doesn't support | 'str' object does not support item assignment |
| Iterator | An object that hands out items one at a time, and is used up after one pass | reversed(name) |
| Lazy | Does the work only when the next item is asked for | reversed() doesn't build a string |
next(it) |
Asks an iterator for its next item | next(reversed("abc")) → 'c' |
| Iterable | Anything you can loop over | a string, a list, an iterator |
| Memory address | Where an object lives in memory; varies on every run | 0x7f5335246a40 |
id(x) |
A number identifying an object while it exists | changes after name = name[::-1] |
| Slice | A part of a sequence: s[start:stop:step] |
s[-3:] → 'lot' |
| Step | How far a slice jumps each time; negative walks backwards | s[::-1], s[::2] |
str.join |
Glues strings from an iterable, with the given string between them | "".join(["a", "b"]) → 'ab' |
range(a, b, step) |
The numbers from a up to (not including) b |
range(3, -1, -1) → 3, 2, 1, 0 |
enumerate |
Gives (index, value) pairs while looping |
for i, ch in enumerate(s) |
repr() |
A value shown as you'd type it, with quotes | repr("") → '' |
| Palindrome | Reads the same forwards and backwards | "Malayalam", "12321" |
| Alphanumeric | A letter or a digit | "A", "3", not "?" |
isalnum() |
True if the character (or every character) is a letter or digit | "?".isalnum() → False |
isalpha() |
True for letters only | "3".isalpha() → False |
lower() |
Returns a lowercase copy | "INDIA".lower() → 'india' |
ord() |
A character's number code | ord("M") → 77 |
| Generator expression | Produces values one at a time, like a comprehension without the list | ch.lower() for ch in s |
| Two pointers | Two indexes moving through the data, here from both ends inwards | i, j in the palindrome check |
| Truthy / falsy | Values that count as True / False in an if |
"e" truthy; "", 0, None falsy |
or |
Returns the first truthy value, or the last value | False or "e" → 'e' |
in (string) |
Is this a substring (a piece) of that string? | "ae" in "aeiou" → True |
| Set | A collection of unique items with O(1) average lookup | set("aeiou") |
| Hash lookup | Jumping straight to an item's slot instead of scanning | ch in VOWELS |
sum(1 for ...) |
Counting the items that pass a test | number of vowels |
Counter |
A dict that counts things; missing keys give 0 | Counter("aab") → {'a': 2, 'b': 1} |
split() / split(" ") |
Split on any whitespace (dropping empties) / on every single space | "a b".split(" ") → ['a', '', 'b'] |
| O(n), O(n²), O(1) | Time or space that grows like n, like n × n, or not at all | one pass; removing each letter; two pointers |
| Brute force | Try every possibility | remove each letter, check the rest |
Summary
- Reverse a string:
strhas no.reverse()(AttributeError), ands[0] = ...raisesTypeError, because strings are immutable.reversed(s)is a lazy iterator, not a string. Uses[::-1](a slice with step −1) or"".join(reversed(s)); without them, loop from the last index down, collect in a list, and join once. O(n) time and space. - Palindrome ignoring case and punctuation:
s == s[::-1]fails on"Malayalam"('M' != 'm') and"Never odd or even"(spaces). Clean withlower()andisalnum()first (O(n) space), or use two pointers from both ends, skipping non-alphanumeric characters, in O(1) extra space. Empty and punctuation-only strings are palindromes. - Count vowels:
ch == "a" or "e"is always true, because"e"is truthy.ch in "aeiou"misses capitals. Lower first, check membership in a set, and count withsum(1 for ...), or useCounterfor each vowel. O(n) time.
Next episode: String questions II: checking anagrams with sorted and with a Counter, finding the first character that doesn't repeat, and the most frequent character when there's a tie.