String Foundations

8 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

A String Is a Row of Characters

A string is text inside quotes, like "garden", which we keep in a variable named s. Python stores it as a row of characters. A character is one letter, one digit, one space or one symbol. Every place in the row has a number called its index, which is its position counted from 0. In "garden" the letter g sits at index 0, a at 1, r at 2, d at 3, e at 4 and n at 5. Write s[3] to read the character at index 3, which is d. Write len(s) to ask how many characters there are: 6. So the last index is always len(s) - 1, here 5, and s[-1] is a shortcut for the last character, n. A slice s[a:b] copies the characters from index a up to, but not including, index b. So s[0:3] is "gar" and s[3:] is "den". A string cannot be changed after it is made; programmers say it is immutable. To turn garden into Garden you build a new string: "G" + s[1:].

The intuition

Counting from 0 makes the index mean "how many steps from the first character". The first character is 0 steps away, so its index is 0. It also explains slices: s[0:3] holds 3 - 0 = 3 characters, and s[3:6] holds the next 3, so two slices side by side never overlap and never leave a gap. Reading s[3] or asking len(s) takes one step however long the string is, because Python jumps straight to that place. A slice has to copy its characters, so s[0:3] costs 3 steps. And since a string cannot change, every edit is really "make a new string": safe, because nobody else's copy is spoiled, but it costs a copy each time.

A real-world analogy

Picture six lockers along a school corridor, numbered from 0 at the door, each holding one letter card: g, a, r, d, e, n. The locker number is the index, and the number of lockers is len. Asking for locker 6 in a row of six means asking for a locker that is not there. A slice is copying the cards from lockers 0, 1 and 2 onto a strip of paper: the lockers still hold their cards. The lockers are sealed, so to change a card you write a fresh strip of paper, which is a new string.

s = "garden"
print(len(s))          # 6 characters
print(s[0])            # g, the first (index 0)
print(s[len(s) - 1])   # n, the last (index 5)
print(s[-2])           # e, second from the end
print(s[0:3])          # gar: indexes 0, 1, 2 (stops before 3)
print(s[3:])           # den: from index 3 to the end
t = "G" + s[1:]        # a string cannot change, so build a new one
print(t)               # Garden
print(s)               # garden: s itself is untouched

Walking Through a String

Most string work means visiting the characters one by one. The simplest way is for ch in w: Python hands you each character in order. For the word "HOME", ch is H, then O, then M, then E. When you also need the index, write for i in range(len(w)). Here range(4) counts 0, 1, 2, 3, so w[i] reads each character and you know where it is. The third way is a while loop: it repeats as long as its condition is true. Start with i = 0, write while i < len(w), and add 1 to i yourself inside the loop with i += 1. Forget that line and the loop never ends. A while loop is handy for two strings at once with one index i. The word "go" has 2 characters and "HOME" has 4, so the condition is i < len(a) or i < len(b); the word or is true when at least one side is true. Inside, guard each read with if i < len(a), so you never read a place that does not exist.

The intuition

A loop over a string of n characters takes about n steps: double the length and you double the steps. People write that as O(n), said "order n": the work grows in step with n. Reading one character, s[i], is O(1), "order one": one step however long the string. The guard if i < len(a) is a tiny question: "does this word still have a character at place i?" If the answer is no, you skip that word for this round. That is why one loop handles words of different lengths with no special case for the leftover tail: when "go" has run out, "HOME" simply carries on alone.

A real-world analogy

Think of reading two lines of text with two fingers held at the same column. Finger one is on the word "go", finger two on "HOME". Both fingers move one column to the right on every beat. When finger one slides off the end of "go" it has nothing to point at, so you skip it, while finger two keeps going until "HOME" ends too. The column is i, the fingers are a[i] and b[i], and "nothing to point at" is the check i < len(a) being false.

a = "go"
b = "HOME"
i = 0                             # the column
while i < len(a) or i < len(b):   # go on while either word has a character here
    x = "-"                       # "-" means: this word has nothing here
    y = "-"
    if i < len(a):                # guard: does a have a place i?
        x = a[i]
    if i < len(b):                # guard: does b have a place i?
        y = b[i]
    print(i, x, y)
    i += 1                        # move to the next column

Handy String Methods

A method is a ready-made action that belongs to a string, and you call it with a dot, like line.lower(). Because a string cannot change, a method never edits the string: it returns a new one. We will use the line " Red Apple pie ", which has two spaces at each end. strip() removes spaces from both ends only, giving "Red Apple pie". lower() turns capitals into small letters, and upper() does the opposite. split() cuts the line into words wherever there are spaces and returns a list, a row of boxes written in square brackets: ['Red', 'Apple', 'pie']. It ignores extra spaces. "-".join(words) does the reverse: it glues the words of a list together with the text before the dot between them. replace("pie", "tart") swaps one piece for another. find("Apple") gives the index where the piece starts, or -1 if it is missing. startswith("Red") answers True or False. isalpha(), isdigit() and isalnum() ask whether the text is all letters, all digits, or all letters and digits.

The intuition

Each method hides a small loop that you would otherwise write by hand. strip walks in from both ends, split walks the whole line once, and join walks the list once. So each costs about n steps, O(n), and each builds a new string or list, which is extra memory of about n. The pair that matters most for tidying text is split() and join(). split() turns messy text with any number of spaces into a tidy list of words, and join() turns the list back into one string with exactly the spacing you choose. Two calls, and the extra spaces are gone, because split() threw them away.

A real-world analogy

A string method is like a tool at a photocopy counter that always works on a copy. The clerk takes your page, trims the blank margins (strip) and hands back a fresh page; your original stays in your bag. split is a paper cutter that slices a long strip at every gap and gives you the pieces in a tray, which is the list. join is the glue stick that sticks the pieces back along one strip with the gap you choose between them.

line = "  Red Apple pie  "              # two spaces at each end
print(line.strip())                     # Red Apple pie
print(line.lower().strip())             # red apple pie
words = line.split()                    # cut at spaces
print(words)                            # ['Red', 'Apple', 'pie']
print("-".join(words))                  # Red-Apple-pie
print(line.replace("pie", "tart"))      # the same line with tart for pie
print(line.find("Apple"))               # 6: the index where Apple starts
print(line.startswith("Red"))           # False: the line starts with a space
print("7".isdigit(), "R".isalpha(), " ".isalnum())   # True True False

Comparing and Checking Membership

Often you must ask a yes-or-no question about characters. == asks whether two strings are exactly equal, letter by letter, capitals included, so "a" == "A" is False. != means not equal. The word in asks whether something is inside something else: "rel" in "Umbrella" is True. To ask "is this letter a vowel?" there are two homes for the five vowels. One is the string "aeiou", and ch in "aeiou" scans it, at most 5 steps. The other is a set, written with curly braces: {"a", "e", "i", "o", "u"}. A set is a bag of distinct items with no order; writing the same item twice keeps one. A set is built so that ch in vowels takes about one step on average, however big the bag is: Python files each item on a shelf worked out from the item itself and goes straight to that shelf. Capitals are different characters, so call ch.lower() first. In "Umbrella" the vowels are U, e and a: 3.

The intuition

With five vowels, scanning is cheap. The set pays off when the bag is large, say all the words of a dictionary: scanning 100,000 items to answer one question costs up to 100,000 steps, while the set answers in about one on average. The lower() trick is the second idea. Instead of listing both u and U, you convert the character once and ask one question. Fewer entries, fewer mistakes. A yes-or-no test is the heart of most string loops: walk the characters, ask a question, update a count. Here the count is the whole result, so the shape is: start at 0, walk, test, add one.

A real-world analogy

A set is a coat-check desk with numbered hooks, where the number for each coat is worked out from the coat itself. To ask if your coat is there, the clerk goes straight to its hook instead of walking along the whole rail. The string "aeiou" is the plain rail: the clerk walks from one end and checks each coat, which is fine for five coats. Calling lower() is hanging every coat with its label facing the same way, so a U and a u end up at the same hook.

vowels = {"a", "e", "i", "o", "u"}   # a set: distinct items, quick to ask "is it inside?"
word = "Umbrella"
count = 0                            # vowels found so far
for ch in word:
    if ch.lower() in vowels:         # lower() so "U" is checked as "u"
        count += 1
print(count)                         # 3 (U, e, a)
print("U" in vowels)                 # False: capital U is a different character
print("rel" in word)                 # True: in also finds a piece inside a string
print(word[3:6] == "rel")            # True: == compares letter by letter

Changing Letters: Use a List

Since a string cannot be changed, the way to change letters in place is to copy them into a list. list("a1b2c") gives ['a', '1', 'b', '2', 'c'], a row of boxes you may rewrite: chars[1] = "x" is allowed. Lists use the same indexes and len as strings. To swap two boxes write chars[i], chars[j] = chars[j], chars[i]; Python reads both boxes first and then stores them crosswise, so no value is lost. When you are done, "".join(chars) glues the boxes back into one string. To reverse a whole row, put one finger at each end. A pointer is just an index variable that points at a box, so left = 0 and right = len(chars) - 1 are two pointers. Swap, move both inward, and stop when left < right is no longer true. Reversing all of a1b2c gives c2b1a. To keep the digits where they are, move each pointer past boxes that are not letters, using isalpha(), and swap only when both rest on letters. The word and is true only when both sides are true, and not flips True to False. The result is c1b2a.

The intuition

Two fingers walking inward never visit a box twice. Each finger moves toward the middle, so together they make at most n moves, and they swap at most n / 2 times. That is O(n) steps, and the only extra memory is the list itself. The skipping loops keep the rule simple: a finger sitting on a box that does not count just moves on. The check left < right inside the skip loops matters: without it a finger could run off the end of the row on a string such as "123" that has no letters at all. And because we only ever swap letters with letters, everything that is not a letter never moves.

A real-world analogy

Imagine five trays on a table in a row, each holding a card. Some trays hold letter cards (a, b, c) and some hold number cards (1, 2). You stand at one end and a friend stands at the other. You both walk toward the middle, stepping past any tray that holds a number card. Whenever you both stand at letter trays, you trade the two cards and each step one tray in. Your position is left, your friend's is right, and when you meet or pass each other the job is done.

chars = list("a1b2c")        # a list of boxes we may change
left = 0                     # finger at the first box
right = len(chars) - 1       # finger at the last box (index 4)
while left < right:          # stop when the fingers meet or cross
    while left < right and not chars[left].isalpha():     # skip digits on the left
        left += 1
    while left < right and not chars[right].isalpha():    # skip digits on the right
        right -= 1
    chars[left], chars[right] = chars[right], chars[left] # swap the two boxes
    left += 1                # both fingers step inward
    right -= 1
print("".join(chars))        # c1b2a

Building a New String

Sometimes the answer is a brand-new string, built piece by piece. The tempting way is result += ch, which means result = result + ch. But a string cannot change, so each += makes a whole new string: Python copies every old character and then adds the new one. Doubling each letter of "tide" gives "ttiiddee", 8 characters, added one at a time. The copies add up: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36 character copies for just 8 characters. The better way is to collect the pieces in a list with append, which adds a box at the end in one step, and to glue them once at the end with "".join(pieces). That is 8 appends plus one join that copies 8 characters: 16 steps. Reversing is easy too. result[::-1] reads the string from the end to the start, so "ttiiddee" becomes "eeddiitt". The same slice works on a list, so "".join(pieces[::-1]) gives the same answer.

The intuition

Why is one big copy better than many small ones? With += the first add copies 1 character, the second 2, and so on up to n: about n x n / 2 copies in all. For 100,000 characters that is about 5,000,000,000 copies. The list way touches each character a fixed number of times: n appends and one join of n, about 2n steps, which is 200,000 for the same string. That is the difference between finishing at once and waiting. The pattern is the same whenever you build text: walk the input, append pieces to a list, join once at the end. Taking two words turn by turn is this exact pattern: use the one-index walk, append a[i] then b[i] with their guards, and join.

A real-world analogy

Think of making a long paper chain. The += way is rebuilding the entire chain from scratch every time you want to add one link: you cut out all the old links again and then add the new one. The list-and-join way is dropping each finished link into a box as you make it, and linking them all together once, at the end, in one sitting. The box is the list, dropping a link in is append, and linking everything is join. Reversing is simply reading the finished chain from its far end.

word = "tide"
pieces = []                      # an empty list to collect pieces in
for ch in word:
    pieces.append(ch)            # append adds one box at the end
    pieces.append(ch)            # the same letter again
result = "".join(pieces)         # one join at the end: one copy
print(result)                    # ttiiddee
print(len(result))               # 8
print(result[::-1])              # eeddiitt: read from the end
print("".join(pieces[::-1]))     # eeddiitt: the same slice works on the list

Repeating, Remainders and GCD

A piece t tiles a string s when s is t written out one or more times in a row. Python repeats a string with *: "xyz" * 3 is "xyzxyzxyz". Take p = "xyzxyzxyz", 9 characters, and q = "xyzxyz", 6 characters. Both are made of "xyz". To test a size you need the remainder. a % b is what is left after fitting as many whole copies of b into a as possible, and a // b is how many whole copies fit. 9 // 3 is 3 and 9 % 3 is 0, so 3 fits 9 exactly. 9 % 6 is 3, so 6 does not. A piece that tiles both strings has a length that fits both 9 and 6 exactly. The biggest such number is their greatest common divisor, written gcd. To compute it, define a function with def. def gcd(a, b) names a recipe, and return hands back the answer. The recipe: while b is not 0, replace the pair (a, b) by (b, a % b). For (9, 6) that gives (6, 3) and then (3, 0), so the answer is 3.

The intuition

Why does the recipe work? Any number that fits exactly into both a and b also fits into the leftover a % b, because the leftover is a minus some whole copies of b. So the pairs (a, b) and (b, a % b) have exactly the same exact fits, and the second pair is smaller. Keep going until the leftover is 0, and the number left is the biggest exact fit. It takes very few rounds: under 30 for any lengths up to 100,000. The second tool is gluing in both orders. If p and q are made of the same piece, then p + q and q + p are the same text. If they have no common piece, the two gluings differ somewhere, so one == test says whether a common piece can exist.

A real-world analogy

You have two rows of floor tiles, one 9 tiles long and one 6 tiles long, and you want to cover both rows with identical strips laid end to end, using the longest strip that fits both rows exactly. A strip of 3 tiles fits the 9-row as 3 strips and the 6-row as 2 strips. A strip of 4 fits neither exactly. gcd finds the longest strip length. The pattern printed on that strip is the common piece. If the two rows are printed with different patterns, no strip can match both.

def gcd(a, b):                # a recipe named gcd, with two inputs
    while b != 0:             # stop when nothing is left over
        a, b = b, a % b       # replace the pair by (b, remainder)
    return a                  # hand back the answer
p = "xyzxyzxyz"
q = "xyzxyz"
size = gcd(len(p), len(q))    # gcd(9, 6) = 3
piece = p[:size]              # the first 3 characters: xyz
print(size, piece)            # 3 xyz
print(piece * (len(p) // size) == p)    # True: xyz 3 times is p
print(piece * (len(q) // size) == q)    # True: xyz 2 times is q
print(p + q == q + p)                   # True: both orders give the same text
print("xyzxyz" + "xyx" == "xyx" + "xyzxyz")   # False: the orders differ

Rewriting a List in Place

Sometimes the new answer must be stored inside the very same list, with no second list. Use two pointers that both start at index 0 and move the same way. read is the finger that looks at the original. write is the finger that marks where the next answer box goes. Take chars = ['a', 'a', 'b', 'c', 'c', 'c'] and shrink each run to its letter followed by its count, with no count when the run has length one. A run is a stretch of identical letters in a row. So aabccc becomes a2bc3, which is 5 boxes. For each run: remember where it starts, move read forward while the letters match, so the run length is read - start, write the letter at write, and if the length is more than 1 write its digits, one per box. str(12) turns the number 12 into the text "12", and a for loop over it gives "1" then "2". At the end the first write boxes hold the answer, and write is the length to report. The boxes after that are leftovers to ignore.

The intuition

Why can we write over the list we are still reading? Because the write finger can never get ahead of the read finger. A run of length 1 reads one box and writes one box. A run of length 2 reads two boxes and writes two (the letter and the digit 2). A run of length 10 reads ten and writes three (the letter, 1 and 0). A run never writes more boxes than it reads, so write stays behind or level with read, and anything it overwrites has already been read. The whole job is one pass: read moves along the list once, so it is O(n) steps, and the only extra memory is a few variables.

A real-world analogy

A clerk is copying a long column of ledger lines into shorter notes, written on the same sheet, starting from the top. Her eyes read down the page (read) and her pen follows behind, writing each short note on the first free line (write). Because a short note is never longer than the lines it summarises, the pen never reaches a line the eyes have not read. When she finishes, the top few lines hold the notes, and the lines below are old text she ignores.

chars = list("aabccc")                  # a list of 6 boxes
write, read = 0, 0                      # both fingers start at the first box
while read < len(chars):                # until read has seen every box
    start = read                        # where this run begins
    while read < len(chars) and chars[read] == chars[start]:
        read += 1                       # move read to just past the run
    chars[write] = chars[start]         # write the run's letter
    write += 1
    if read - start > 1:                # run length is read - start
        for digit in str(read - start): # str(12) is "12": one digit per box
            chars[write] = digit
            write += 1
print(write, chars[:write])             # 5 ['a', '2', 'b', 'c', '3']

All DSA learning paths