SyntaxPilot
Courses/Python Coding Questions/Lesson 15
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 15 of 30

String questions V

string building in a loop (+= vs "".join)caesar cipher with ord/chrcheck if one string is a rotation of another

These are the notes for Python Coding Questions, episode 15, the fifth and last round of string questions. Three questions that come up in placement interviews: building a long string in a loop (why += can get slow and "".join doesn't), the caesar cipher (letters as numbers with ord and chr, wrapped with % 26), and checking whether one string is a rotation of another (the a + a trick, and the length check it needs). Along the way you'll see a loop timed for real that gets four times slower when the input doubles, TypeError: sequence item 2: expected str instance, int found, a cipher that turns xyz into {|}, and a rotation check that says yes to a substring.

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: timings (they change from run to run and from computer to computer; each one shown here is a representative run) and tracebacks, which show the full path to your file; here it is shortened to main.py.

Q1: Building a long string in a loop (+= vs "".join)

Real-life example: a chai stall writes one line on the bill for every order: chai 10. By night there are thousands of lines. Imagine a shopkeeper who, for every new order, copies the whole bill onto a fresh page and then adds one line. The more orders, the more copying. A smarter shopkeeper puts each slip on a spike and glues them together once, at night.

The question: build one big string out of many small pieces (lines of a bill, rows of a CSV file, words of a sentence), as fast as possible.

Ask the interviewer: how many pieces, roughly? Is there a separator between the pieces (a newline, a comma, a space)? Are all the pieces already strings?

Attempt 1: bill += line

The obvious way: start with an empty string and add one line per order. Time it for 25,000, 50,000 and 100,000 orders with time.perf_counter(), a clock for timing short pieces of code (call it before and after, and subtract).

import time

for n in [25_000, 50_000, 100_000]:
    start = time.perf_counter()
    bill = ""
    for i in range(n):
        bill += "chai 10\n"      # one line per order
    print(n, "orders:", round(time.perf_counter() - start, 2), "seconds")

Output:

25000 orders: 0.06 seconds
50000 orders: 0.25 seconds
100000 orders: 1.24 seconds

(25_000 is just 25000: Python lets you put underscores in numbers to make them easier to read.)

Twice the orders, about four times the time. That's the fingerprint of O(n²) (quadratic) work: double n, and n × n becomes four times bigger.

Why: strings are immutable

A Python string is immutable: once it's made, it can never change. So bill += line can't add to the old bill. It builds a brand new string, copies every character of the old bill into it, adds the line, and the old string is thrown away.

Order number Characters copied by this +=
1 8
2 16
3 24
... ...
n 8 × n

Adding all of those up gives about 8 × n²/2 characters copied. For 100,000 orders, that's about 40 billion character copies. That's the shopkeeper rewriting the whole bill for every order.

You can check that += makes a new string with is, which tells you whether two names point to the very same object:

a = "chai"
b = a                   # b and a are the same string
a += " 10"              # a new string is made for a
print(a, "|", b)
print(a is b)

Output:

chai 10 | chai
False

b still holds the old string: += didn't change it, it made a new one and moved the name a to it.

The fix: collect the pieces in a list, then "".join once

A list is mutable: it can grow. lines.append(line) puts one more item at the end without copying the others (on average O(1)). At the end, "".join(lines) is called on the separator (here the empty string: nothing between the pieces). It adds up the total length once, makes one string of exactly that size, and copies each piece once: O(n) in total.

import time

start = time.perf_counter()
lines = []
for i in range(100_000):
    lines.append("chai 10\n")    # a list grows cheaply
bill = "".join(lines)              # one copy at the end
print(len(bill), "characters")
print(round(time.perf_counter() - start, 4), "seconds")

Output:

800000 characters
0.0041 seconds

The same 800,000-character bill, in a few thousandths of a second: hundreds of times faster than the += loop.

An honest note: CPython's += shortcut

CPython is the standard Python (the one you download from python.org, and the one SyntaxPilot runs). It has an optimisation: when a string is a local variable inside a function and nothing else points to it, += can sometimes grow it in place instead of copying. So the same loop inside a function can be fast:

import time

def build_plus(n):
    bill = ""
    for i in range(n):
        bill += "chai 10\n"
    return bill

def build_join(n):
    lines = []
    for i in range(n):
        lines.append("chai 10\n")
    return "".join(lines)

for f in (build_plus, build_join):
    start = time.perf_counter()
    f(100_000)
    print(f.__name__, round(time.perf_counter() - start, 4), "seconds")

Output:

build_plus 0.0045 seconds
build_join 0.0027 seconds

Don't rely on it. It's an implementation detail: it doesn't work at the top level of a script (as you saw above), it stops working as soon as a second name points to the string, and other Pythons (PyPy, for example) don't do it at all. "".join is always linear, and it's what interviewers expect.

The join trap: everything must be a string

words = ["masala", "chai", 10]
print(" ".join(words))

Output:

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    print(" ".join(words))
          ~~~~~~~~^^^^^^^
TypeError: sequence item 2: expected str instance, int found

join only glues strings; it never converts anything for you. "Sequence item 2" is the item at index 2, the number 10. Convert each item with str() first. The separator can be any string, and join even works on a string, because a string is a sequence of characters:

words = ["masala", "chai", 10]
print(" ".join(str(w) for w in words))
print(", ".join(["dal", "roti", "sabzi"]))
print("-".join("2026"))

Output:

masala chai 10
dal, roti, sabzi
2-0-2-6

str(w) for w in words is a generator expression: it hands join one converted item at a time, without building another list first.

Complexity: O(n) time for the appends plus O(n) for the join, where n is the total number of characters. O(n) space for the list and the final string.

Q2: The caesar cipher

Real-life example: two friends pass a secret note in class: meet at 5. They shift every letter 3 places forward in the alphabet: a becomes d, b becomes e, m becomes p. The friend shifts back by 3 to read it. This is the caesar cipher, one of the oldest codes in the world (Julius Caesar is said to have used a shift of 3). And what comes 3 places after x, y and z? The alphabet should go round like a clock: a, b, c.

The question: write caesar(text, shift) that shifts every letter by shift places, wrapping around after z. Keep capital letters capital, and leave anything that isn't a letter (spaces, digits, punctuation) unchanged. Decoding should be caesar(secret, -shift).

Call Result
caesar("abc", 3) 'def'
caesar("xyz", 3) 'abc'
caesar("Meet at 5, Zoya!", 3) 'Phhw dw 5, Crbd!'
caesar("abc", -1) 'zab'

Letters are numbers: ord and chr

To shift a letter, we need it as a number. Every character has a number called its Unicode code point. ord(ch) gives the number of a character, and chr(n) gives the character for a number. The lowercase letters are 97 to 122, and the capitals 65 to 90, in alphabet order.

print(ord("a"), ord("b"), ord("z"))
print(ord("A"), ord("Z"), ord(" "), ord("5"))
print(chr(97), chr(100), chr(123))

Output:

97 98 122
65 90 32 53
a d {

Attempt 1: chr(ord(ch) + shift)

def caesar(text, shift):
    out = ""
    for ch in text:
        out += chr(ord(ch) + shift)
    return out

print(ord("a"), ord("b"), chr(100))
print(caesar("abc", 3))
print(caesar("xyz", 3))
print(caesar("Meet at 5", 3))

Output:

97 98 d
def
{|}
Phhw#dw#8

abc becomes def, correct. But xyz becomes {|}, the space became # and 5 became 8.

Why it fails

The code points don't stop at z (122). After it come { (123), | (124), } (125). Nothing told the numbers to go back to a. And we shifted everything, including spaces (32 + 3 = 35, which is #) and digits.

The fix: work with the position in the alphabet, and wrap with % 26

  1. Turn the letter into its position in the alphabet: ord(ch) - ord("a") is 0 for a, up to 25 for z.
  2. Add the shift, then take % 26, the remainder after dividing by 26. That turns a straight line of numbers into a circle: 25 + 3 = 28, and 28 % 26 = 2, which is c.
  3. Turn the position back into a letter: chr(ord("a") + position).

Capital letters have their own range, so their base is ord("A") instead. Anything else is kept as it is.

Letter Position + 3 % 26 Result
a 0 3 3 d
w 22 25 25 z
x 23 26 0 a
z 25 28 2 c

In Python, % with a positive number on the right always gives a result from 0 to 25, even when the left side is negative. So shifting back works with the same line:

print(28 % 26, 26 % 26, 3 % 26)
print(-1 % 26, -3 % 26, (0 - 3) % 26)
print(29 % 26)       # a shift of 29 is the same as 3

Output:

2 0 3
25 23 23
3

(This is different from C, C++ and Java, where -1 % 26 is -1. In Python the result takes the sign of the right-hand side.)

def caesar(text, shift):
    out = []
    for ch in text:
        if ch.islower():
            base = ord("a")
        elif ch.isupper():
            base = ord("A")
        else:
            out.append(ch)               # spaces, digits stay
            continue
        pos = (ord(ch) - base + shift) % 26   # 0..25, wraps
        out.append(chr(base + pos))
    return "".join(out)

secret = caesar("Meet at 5, Zoya!", 3)
print(secret)
print(caesar(secret, -3))               # shift back to decode
print(caesar("xyz", 3), caesar("abc", 29), caesar("abc", -1))

Output:

Phhw dw 5, Crbd!
Meet at 5, Zoya!
abc def zab

The space, the 5, the comma and the ! stayed. Capital Z wrapped to capital C. Shifting by -3 gives the note back. A shift of 29 is the same as 3, and -1 turns a into z. Notice we used a list and "".join from question one.

ch.islower() is True for a lowercase letter, ch.isupper() for a capital. continue skips the rest of the loop body and goes to the next character.

One caution: islower() is also True for lowercase letters outside the English alphabet, like é or ß. The formula above would then give a wrong letter. If the input can contain them, test for the English letters only: "a" <= ch <= "z" and "A" <= ch <= "Z".

ord takes exactly one character

print(ord("ab"))

Output:

Traceback (most recent call last):
  File "main.py", line 1, in <module>
    print(ord("ab"))
          ~~~^^^^^^
TypeError: ord() expected a character, but string of length 2 found

The ready-made tools: string.ascii_lowercase and str.translate

Once you understand the formula, Python can do the whole shift with a translation table: str.maketrans(from, to) builds a table that maps each character of from to the character at the same position in to, and text.translate(table) applies it to every character at once.

import string

def caesar(text, shift):
    lower, upper = string.ascii_lowercase, string.ascii_uppercase
    k = shift % 26
    table = str.maketrans(lower + upper, lower[k:] + lower[:k] + upper[k:] + upper[:k])
    return text.translate(table)

print(string.ascii_lowercase)
print(caesar("Meet at 5, Zoya!", 3))
print(caesar("Phhw dw 5, Crbd!", -3))

Output:

abcdefghijklmnopqrstuvwxyz
Phhw dw 5, Crbd!
Meet at 5, Zoya!

lower[3:] + lower[:3] is the alphabet rotated by 3: defg...xyzabc. That's question three's idea already.

Complexity: O(n) time, one step per character; O(n) space for the result.

Q3: Is one string a rotation of another?

Real-life example: four friends sit at a round table: A, B, C, D going clockwise. They all get up and move two seats. Starting from the same chair, it now reads C, D, A, B: same people, same neighbours, just turned. That's a rotation: cut the string somewhere and swap the two parts. "waterbottle" cut after wat gives "erbottle" + "wat" = "erbottlewat". But A, C, B, D has the same people with different neighbours: not a rotation.

The question: given strings a and b, is b a rotation of a?

a b Rotation?
"waterbottle" "erbottlewat" yes
"abcd" "cdab" yes
"abcd" "acbd" no (same letters, different order)
"abcd" "bc" no (a piece, not the whole)
"aab" "aba" yes
"" "" yes

Attempt 1: same letters? Compare them sorted

def is_rotation(a, b):
    return sorted(a) == sorted(b)

print(is_rotation("waterbottle", "erbottlewat"))
print(is_rotation("abcd", "cdab"))
print(is_rotation("abcd", "acbd"))

Output:

True
True
True

The third one is True, but acbd is the shuffled table. Why? Sorting throws the order away. It checks that the same people are at the table, not who sits next to whom. That's the anagram check from episode 12; a rotation is much stricter.

Attempt 2: try every cut point

Do exactly what a rotation is: the lengths must match, and for every cut point i, a[i:] + a[:i] is one rotation. If any of them equals b, it's a rotation.

import time

def is_rotation(a, b):
    if len(a) != len(b):
        return False
    for i in range(len(a)):
        if a[i:] + a[:i] == b:           # cut at i, swap the halves
            return True
    return len(a) == 0

print(is_rotation("abcd", "cdab"), is_rotation("abcd", "acbd"))
a = "ab" * 100_000                        # 200,000 letters
b = "ab" * 99_999 + "ba"                 # not a rotation
start = time.perf_counter()
print(is_rotation(a, b), round(time.perf_counter() - start, 2), "seconds")

Output:

True False
False 2.33 seconds

Correct now, but the big test takes seconds. Why? There are n cut points, and every cut builds a new string of length n with slicing and +. n × n: O(n²). (Why is b not a rotation? Every rotation of "abab...ab" still alternates letters; b ends with "abba", two bs in a row.)

The last line, return len(a) == 0, handles two empty strings: the loop never runs, and "" is a rotation of "".

The fix: every rotation lives inside a + a

Write a twice in a row: it's like walking round the table twice. Every rotation of a appears inside a + a, starting at position 0, 1, 2, ... n − 1:

a = "abcd"
doubled = a + a
print(doubled)
for i in range(len(a)):
    print(i, doubled[i:i + len(a)])

Output:

abcdabcd
0 abcd
1 bcda
2 cdab
3 dabc

So b is a rotation of a when b is a substring of a + a. Python's in operator searches for a substring.

Attempt 3: b in a + a (and the trap)

def is_rotation(a, b):
    return b in a + a

print(is_rotation("abcd", "cdab"), is_rotation("abcd", "acbd"))
print(is_rotation("abcd", "bc"))

Output:

True False
True

"bc" says True. Why? in finds any substring, of any length. A rotation must use every letter. So check that the lengths are equal first.

The final version

import time

def is_rotation(a, b):
    return len(a) == len(b) and b in a + a

tests = [("waterbottle", "erbottlewat"), ("abcd", "cdab"), ("abcd", "acbd"),
         ("abcd", "bc"), ("aab", "aba"), ("", ""), ("a", "")]
for a, b in tests:
    print(repr(a), repr(b), is_rotation(a, b))
a = "ab" * 100_000
b = "ab" * 99_999 + "ba"
start = time.perf_counter()
print(is_rotation(a, b), round(time.perf_counter() - start, 4), "seconds")

Output:

'waterbottle' 'erbottlewat' True
'abcd' 'cdab' True
'abcd' 'acbd' False
'abcd' 'bc' False
'aab' 'aba' True
'' '' True
'a' '' False
False 0.0005 seconds

Every case is right, and the big test takes under a millisecond instead of seconds. and short-circuits: if the lengths differ, Python never builds a + a at all.

Complexity: building a + a is O(n). CPython's substring search is fast in practice (for long patterns it uses an algorithm called "two-way" that is linear in the worst case, in recent versions). O(n) space for a + a. If an interviewer asks for a guaranteed linear search you write yourself, the answer is the KMP algorithm (Knuth-Morris-Pratt), covered in the DSA course.

Follow-up: how far was it turned?

(a + a).find(b) gives the position where b starts inside a + a, which is the cut point: how many seats everyone moved. find returns -1 when it isn't there.

def rotation_amount(a, b):
    if len(a) != len(b):
        return -1
    return (a + a).find(b)

print(rotation_amount("abcd", "cdab"))
print(rotation_amount("waterbottle", "erbottlewat"))
print(rotation_amount("abcd", "acbd"))

Output:

2
3
-1

Common mistakes (and what you really see)

Mistake What you see Why Fix
bill += line in a long loop 25k / 50k / 100k lines: about 0.06 / 0.25 / 1.3 s strings are immutable: every += copies the whole string lines.append(line), then "".join(lines)
" ".join(["masala", "chai", 10]) TypeError: sequence item 2: expected str instance, int found join never converts " ".join(str(x) for x in items)
",".join forgetting the separator goes between "a,b,c", not "a,b,c," join puts the separator only between pieces add the ending yourself if you need it
lines.join("") AttributeError: 'list' object has no attribute 'join' join is a string method "".join(lines)
chr(ord(ch) + shift) "xyz" → "{|}" code points go past z (ord(ch) - base + shift) % 26
shifting every character "Meet at 5" → "Phhw#dw#8" spaces and digits shifted too only shift letters, keep the rest
one base for all letters capitals come out as wrong characters capitals are 65..90, lowercase 97..122 base = ord("A") for capitals
ord("ab") TypeError: ord() expected a character, but string of length 2 found ord takes one character loop over the characters
sorted(a) == sorted(b) for a rotation "acbd" → True sorting forgets the order b in a + a
trying every cut about 2.4 s for 200,000 letters O(n²) b in a + a, O(n)
b in a + a alone "bc" → True any substring matches len(a) == len(b) and ...

Here are the two errors from the table you haven't seen yet, run for real:

lines = ["chai 10", "samosa 15"]
print(",".join(["a", "b", "c"]))
print(lines.join(""))

Output:

a,b,c
Traceback (most recent call last):
  File "main.py", line 3, in <module>
    print(lines.join(""))
          ^^^^^^^^^^
AttributeError: 'list' object has no attribute 'join'

Your turn: crack the code (solution)

You found a secret note, "Wkh fkdl lv uhdgb", but nobody told you the shift. Try every shift from 0 to 25 and print each try with its number; one line will be readable English. This is called a brute-force attack: with only 26 possible keys, trying them all takes no time, which is why the caesar cipher is a puzzle, not real security.

Solution

Decoding with shift k is caesar(note, -k).

def caesar(text, shift):
    out = []
    for ch in text:
        if ch.islower():
            base = ord("a")
        elif ch.isupper():
            base = ord("A")
        else:
            out.append(ch)
            continue
        out.append(chr(base + (ord(ch) - base + shift) % 26))
    return "".join(out)

note = "Wkh fkdl lv uhdgb"
for k in range(26):
    print(k, caesar(note, -k))

Output:

0 Wkh fkdl lv uhdgb
1 Vjg ejck ku tgcfa
2 Uif dibj jt sfbez
3 The chai is ready
4 Sgd bgzh hr qdzcx
5 Rfc afyg gq pcybw
6 Qeb zexf fp obxav
7 Pda ydwe eo nawzu
8 Ocz xcvd dn mzvyt
9 Nby wbuc cm lyuxs
10 Max vatb bl kxtwr
11 Lzw uzsa ak jwsvq
12 Kyv tyrz zj ivrup
13 Jxu sxqy yi huqto
14 Iwt rwpx xh gtpsn
15 Hvs qvow wg fsorm
16 Gur punv vf ernql
17 Ftq otmu ue dqmpk
18 Esp nslt td cploj
19 Dro mrks sc bokni
20 Cqn lqjr rb anjmh
21 Bpm kpiq qa zmilg
22 Aol johp pz ylhkf
23 Znk ingo oy xkgje
24 Ymj hmfn nx wjfid
25 Xli glem mw viehc

Shift 3: "The chai is ready". A program can even pick it for you by counting how many common English words each try contains:

def caesar(text, shift):
    out = []
    for ch in text:
        if ch.islower():
            base = ord("a")
        elif ch.isupper():
            base = ord("A")
        else:
            out.append(ch)
            continue
        out.append(chr(base + (ord(ch) - base + shift) % 26))
    return "".join(out)

COMMON = {"the", "is", "a", "and", "of", "to", "in", "it", "ready", "chai"}
note = "Wkh fkdl lv uhdgb"
best = max(range(26), key=lambda k: sum(w in COMMON for w in caesar(note, -k).lower().split()))
print(best, caesar(note, -best))

Output:

3 The chai is ready

sum(w in COMMON for w in ...) adds up True (1) and False (0), so it counts the common words; max(range(26), key=...) picks the shift with the most.

Practice questions (with solutions)

1. Reverse the words of a sentence. "chai is ready" → "ready is chai". Extra spaces between words should not matter.

Solution

split() with no argument splits on any run of spaces and drops empty pieces (episode 13); [::-1] reverses the list; " ".join glues it back.

def reverse_words(s):
    return " ".join(s.split()[::-1])

print(repr(reverse_words("chai is ready")))
print(repr(reverse_words("  hello    world  ")))
print(repr(reverse_words("")))

Output:

'ready is chai'
'world hello'
''

O(n) time and space.

2. ROT13. ROT13 is a caesar shift of 13. Show that applying it twice gives the original text, and explain why.

Solution

There are 26 letters, and 13 + 13 = 26, so two shifts of 13 go all the way round the circle: (p + 13 + 13) % 26 == p. ROT13 is its own decoder. Python even has it built in as a codec.

import codecs

def caesar(text, shift):
    out = []
    for ch in text:
        if ch.islower():
            base = ord("a")
        elif ch.isupper():
            base = ord("A")
        else:
            out.append(ch)
            continue
        out.append(chr(base + (ord(ch) - base + shift) % 26))
    return "".join(out)

once = caesar("Meet at 5, Zoya!", 13)
print(once)
print(caesar(once, 13))
print(codecs.encode("Meet at 5, Zoya!", "rot13"))

Output:

Zrrg ng 5, Mbln!
Meet at 5, Zoya!
Zrrg ng 5, Mbln!

3. Build a CSV line. Given a list of rows (each a list of values, some numbers), build the text of a CSV file: values joined by commas, rows joined by newlines.

Solution

Two joins: the inner one per row (convert each value with str), the outer one for the lines.

rows = [["item", "qty", "price"], ["chai", 2, 10], ["samosa", 3, 15]]
text = "\n".join(",".join(str(v) for v in row) for row in rows)
print(text)

Output:

item,qty,price
chai,2,10
samosa,3,15

(For real CSV files, with commas or quotes inside values, use the csv module, which handles quoting for you.)

4. Are two strings rotations, ignoring case? "Chai" and "aich" should be True.

Solution

Normalise both first with casefold() (a stronger lower() meant for comparisons), then use the same check.

def is_rotation_ignore_case(a, b):
    a, b = a.casefold(), b.casefold()
    return len(a) == len(b) and b in a + a

print(is_rotation_ignore_case("Chai", "aich"))
print(is_rotation_ignore_case("Chai", "iach"))

Output:

True
False

5. Rotate a string by k. Write rotate_left(s, k) and rotate_right(s, k), where k may be larger than the length.

Solution

Rotating left by k is s[k:] + s[:k]. Take k % len(s) first so a large k works, and guard the empty string (% 0 would be a ZeroDivisionError). Rotating right by k is rotating left by -k, and Python's % makes that positive.

def rotate_left(s, k):
    if not s:
        return s
    k %= len(s)
    return s[k:] + s[:k]

def rotate_right(s, k):
    return rotate_left(s, -k)

print(rotate_left("abcdef", 2), rotate_right("abcdef", 2))
print(rotate_left("abcdef", 8), rotate_right("abcdef", 13))
print(repr(rotate_left("", 3)))

Output:

cdefab efabcd
cdefab fabcde
''

6. A vigenère cipher (a caesar cipher with a key word). Shift each letter by the matching letter of a key word (a = 0, b = 1, ...), repeating the key. vigenere("attack at dawn", "lemon") → "lxfopv ef rnhr".

Solution

Keep a separate counter j for the key that only moves on letters, so spaces don't use up key letters.

def vigenere(text, key, sign=1):
    out = []
    j = 0
    for ch in text:
        if "a" <= ch <= "z":
            shift = ord(key[j % len(key)]) - ord("a")
            out.append(chr(ord("a") + (ord(ch) - ord("a") + sign * shift) % 26))
            j += 1
        else:
            out.append(ch)
    return "".join(out)

secret = vigenere("attack at dawn", "lemon")
print(secret)
print(vigenere(secret, "lemon", -1))

Output:

lxfopv ef rnhr
attack at dawn

Quick quiz

What does this print?

print("-".join("chai"))
print(chr(ord("y") + 2))

(A) chai- then a (B) c-h-a-i then { (C) c-h-a-i then a (D) TypeError

Answer

(B). join works on any sequence of strings, and a string is a sequence of characters, so the dash goes between the letters. ord("y") is 121; plus 2 is 123, and chr(123) is {. Nothing wraps unless you use % 26.

print("-".join("chai"))
print(chr(ord("y") + 2))

Output:

c-h-a-i
{

Interview questions

  1. Why can s += piece in a loop be O(n²)? Strings are immutable, so each += builds a new string and copies everything so far. The copies add up to about n²/2 characters.
  2. What's the fast way, and why is it O(n)? Append the pieces to a list (amortised O(1) each), then "".join(pieces) once: it computes the total length, allocates one string, and copies each piece once.
  3. Doesn't CPython optimise +=? Sometimes, for a local variable with no other references, it resizes in place. It's an implementation detail (not at module level, not when another name refers to the string, not in PyPy), so don't rely on it.
  4. What does "".join([1, 2]) do? TypeError: sequence item 0: expected str instance, int found. Convert first: "".join(map(str, items)).
  5. What are ord and chr? ord gives a character's Unicode code point (ord("a") is 97); chr is the reverse (chr(97) is 'a').
  6. How do you wrap a caesar shift? Work with the position: (ord(ch) - base + shift) % 26, with base = ord("a") or ord("A"), and leave non-letters alone.
  7. Why does decoding with a negative shift work in Python? Python's % with a positive divisor always returns 0..25, even for negative numbers (-1 % 26 is 25). In C or Java it would be -1.
  8. Is the caesar cipher secure? No: there are only 26 keys, so trying them all (a brute-force attack) breaks it instantly. Real encryption uses algorithms like AES with huge keys.
  9. How do you check if b is a rotation of a? len(a) == len(b) and b in a + a. Every rotation of a is a substring of a + a; the length check rules out shorter substrings.
  10. Why not sorted(a) == sorted(b)? That's an anagram check; it ignores the order. "acbd" has the same letters as "abcd" but isn't a rotation.
  11. What's the complexity of the a + a check? O(n) to build a + a, plus the substring search, which is linear in practice; KMP guarantees O(n).

Glossary

Term Meaning Example
Immutable Can't be changed after it's made; "changing" it makes a new object strings, ints, tuples
Mutable Can be changed in place lists, dicts, sets
+= on a string Builds a new string from the old one plus the piece s += "x"
str.join(iterable) Glues the strings of an iterable with the separator between them "-".join(["a", "b"]) → 'a-b'
Separator The string join is called on; it goes between the pieces ", " in ", ".join(...)
list.append(x) Adds one item at the end of a list lines.append("chai 10")
Amortised O(1) O(1) on average over many operations, even if one is sometimes slower append
time.perf_counter() A clock for timing short pieces of code time.perf_counter() - start
O(n), O(n²) Work that grows like n, or like n × n join; += in a loop
Quadratic O(n²): double the input, four times the work 50k → 100k lines: 0.25 s → 1.3 s
CPython The standard Python implementation, written in C what python3 usually runs
PyPy Another Python implementation, with a just-in-time compiler
id() / is An object's identity / whether two names point to the same object a is b
Generator expression (f(x) for x in items): makes items one at a time str(w) for w in words
str(x) Turns a value into text str(10) → '10'
TypeError An operation the types don't support "".join([10])
Caesar cipher Shift every letter by a fixed number of places shift 3: abc → def
Shift / key How many places each letter moves 3
Encode / decode Turn a message into code / back into the message caesar(s, 3) / caesar(s, -3)
Unicode code point The number of a character a is 97, A is 65
ord(ch) The code point of one character ord("a") → 97
chr(n) The character with code point n chr(100) → 'd'
Position in the alphabet ord(ch) - ord("a"): 0 for a, 25 for z ord("x") - 97 → 23
Base The code point of the first letter of the range ord("a") or ord("A")
% (modulo) The remainder after division; in Python, same sign as the divisor 28 % 26 → 2, -1 % 26 → 25
Wrap around Going past the end and starting again at the beginning z + 1 → a
islower() / isupper() True for a lowercase / capital letter "Z".isupper() → True
continue Skip the rest of this loop step
string.ascii_lowercase The text 'abcdefghijklmnopqrstuvwxyz'
str.maketrans / translate Build a character-for-character table / apply it the caesar one-liner
ROT13 A caesar shift of 13; applying it twice gives the original codecs.encode(s, "rot13")
Brute-force attack Trying every possible key 26 shifts
Vigenère cipher A caesar shift that changes with each letter of a key word key lemon
Rotation Cut a string and swap the two parts "cdab" from "abcd"
Cut point Where the string is cut for a rotation a[i:] + a[:i]
Substring A part of a string with no gaps "bc" in "abcd"
in (strings) True if one string is a substring of another "bc" in "abcd"
str.find(sub) The index where sub starts, or -1 "abcdabcd".find("cdab") → 2
Anagram The same letters in any order "acbd" and "abcd"
Short-circuit and / or stop as soon as the answer is known len(a) == len(b) and b in a + a
KMP Knuth-Morris-Pratt: a substring search that is always O(n + m) DSA course
casefold() A stronger lower() for comparing text "Chai".casefold() → 'chai'
Edge case An unusual input that often breaks code "", "xyz", "bc"

Summary

  • += vs join: strings are immutable, so += in a long loop copies the whole string every time: O(n²), and doubling the input made it about four times slower (1.3 s for 100,000 lines). Append the pieces to a list and "".join them once: O(n), a few milliseconds. join only accepts strings: convert with str() first, or you get TypeError: sequence item 2: expected str instance, int found.
  • Caesar cipher: ord turns a letter into a number and chr turns it back. Shifting the number directly runs past z (xyz → {|}). Use the position in the alphabet and wrap with % 26: chr(base + (ord(ch) - base + shift) % 26), with base ord("a") or ord("A"), leaving non-letters alone. Decode with -shift; Python's % keeps it in 0..25.
  • Rotation: sorting ignores order ("acbd" → True), and trying every cut is O(n²) (2.4 s for 200,000 letters). Every rotation of a is inside a + a, so len(a) == len(b) and b in a + a does it in O(n); without the length check, "bc" passes.

Next episode: Dictionary questions: inverting a dictionary when values repeat, merging dictionaries (| and a deep merge), and safely getting a nested value by a path like "a.b.c".