Strings

A log line arrives as one string: " Load the TABLE ". At work you would trim it, lowercase it and split it into words with SQL's TRIM, LOWER and a split function, or with Python's string methods, and move on.

In an interview the same moves come with a twist: find the length of the last word without splitting, reverse the order of the words, ignore everything that is not a letter. To answer those you need to see a string the way Python does: a row of characters, numbered from 0, that never changes.

This lesson covers strings: reading them by position, walking them from either end, and building new ones. Every string tool here is a loop you could write yourself, so we show the loop first. That way you always know what a tool does at the edges and what it costs. The next lesson adds the tools that work on several values at once: tuples, dicts and sorting.

#A string is a row of characters

A string is a sequence of characters, and you read it like a list. s = "spark" holds five characters at positions 0 to 4. len(s) is 5, s[0] is "s", and negative positions count from the end, so s[-1] is "k". A single character is itself a string of length 1.

Slices work as they do for lists: s[1:4] starts at position 1 and stops before position 4. Leave out the start and the slice begins at 0; leave out the stop and it runs to the end. So s[:2] is "sp" and s[2:] is "ark". A third number is the step, how far each move goes. A step of -1 walks backwards, and with the start and stop left out it covers the whole string: s[::-1] is "kraps".

The trace below draws s as a row of cells, with an arrow for the position i. Before you step through, guess what line 3 prints.

▶1s = "spark"
2print(len(s), s[0], s[-1])
3print(s[1:4])
4for i in range(len(s)):
5    print(i, s[i])

(nothing printed yet)

You can also loop over the characters themselves. for c in s: hands out "s", "p", "a", "r", "k", the way for x in nums: hands out items. Use positions when you need a neighbor, or a different order.

word = "pipeline"
print(word[0], word[-1])
print(word[:4])
print(word[4:])
print(len(word))

Walking from the end

Some answers sit at the end of a string: the last word, a file extension, the spaces at the end (called trailing spaces). Then the walk starts at the last position, len(s) - 1, and moves left. A while loop fits, because it stops the moment its condition fails. Here we look for the last space in "big data", which tells us where the last word starts. Guess first: at which position does i stop?

▶1s = "big data"
2i = len(s) - 1
3while i >= 0 and s[i] != " ":
4    i -= 1
5print(i, s[i + 1:])

(nothing printed yet)

Why test i >= 0 at all? Because a negative position is legal in Python: s[-1] is the last character, not an error. Without the test, a string with no space would not stop at the start. It would read the string again from the end until the positions ran out and Python raised an IndexError. Put i >= 0 first: and checks its left side first and skips the right side when the left is false (the short-circuiting from lesson 3), so s[i] is never read with a negative i.

Work the same loop by hand on a string with no space, the case where i >= 0 does its job.

s = "etl"
i = len(s) - 1
while i >= 0 and s[i] != " ":
    i -= 1
print(i, s[i + 1:])

The next problem needs two of these walks, one after the other. The string may end in spaces, so first move left past them. Then move left through the last word, counting letters, and stop at a space or at the start.

The counting walk is the loop you traced, with a counter added. The problem's solution also shows a one-line version with split, a tool this lesson covers below. If an interviewer asks for a version without split, the walk is it: it reads only the end of the string and builds no list.

So far: a string is a row of characters with positions from 0, read with s[i], slices and loops like a list. To find something at the end, start at len(s) - 1 and walk left, testing i >= 0 before s[i].

#Strings never change: build a list, then join

Try to change one character and Python refuses:

s = "spark"
s[0] = "S"   # TypeError: 'str' object does not support item assignment

A string cannot be changed after it is made. The word for this is immutable. No string method changes the string it is called on: s.upper() hands back a new string, "SPARK", and s is still "spark". To get "Spark", you build a new string: "S" + s[1:].

So to build a string piece by piece, collect the pieces in a list and join them once at the end. "".join(pieces) glues a list of strings into one, with nothing between them. Adding to a string with += in a loop also works, but in general each += makes a new string and copies everything built so far, so the copying grows with every piece.

Here is the pattern on a cleanup familiar from data work: keep only letters and digits, in lowercase. Two methods do the per-character work. c.isalnum() is True when c is a letter or a digit, and c.lower() hands back the lowercase version. Guess what clean("Top 3.") returns before you step through.

▶1def clean(s):
2    out = []
3    for c in s:
4        if c.isalnum():
5            out.append(c.lower())
6    return "".join(out)

(nothing printed yet)

Characters are numbers

Every character has a number, its code. ord(c) gives the code of c, and chr(k) gives the character whose code is k. The lowercase letters have the codes 97 to 122, in alphabetical order, so subtracting the code of "a" turns a letter into its place in the alphabet, counting from 0:

ord(c) - ord("a") maps the letters a to z onto the positions 0 to 25. The last row is the warning: capitals have their own codes, 65 to 90, so lowercase first or check the range. chr goes back the other way: chr(ord("a") + 2) is "c".

So a plain list of 26 numbers can count letters: position 0 counts the a's, position 25 the z's. The trace counts the letters of "dead". [0] * 26 makes a list of 26 zeros (* on a list repeats its items). Before you step through, guess what the last line prints: the counts for a, b, c, d and e.

▶1counts = [0] * 26
2for c in "dead":
3    counts[ord(c) - ord("a")] += 1
4print(counts[:5])

(nothing printed yet)

The list holds 26 counters however long the string is, so it costs O(1) extra space, and the walk costs one step per character, O(n) time. The next lesson counts with a dict instead, which works for any character, and for whole words too.

For practice, the bank has To lower case (LeetCode 709): lower a string by hand with ord and chr, building the answer in a list. Try it after this lesson.

Words: split and join

s.split() with no argument cuts a string into its words. It splits at every run of spaces (one or more spaces side by side) and drops the spaces at both ends. sep.join(words) goes the other way: it glues a list of strings into one, with sep between neighbors.

To walk the words from last to first with a for loop, give range a third number. range(start, stop, step) moves by step each time and stops before stop. A step of -1 counts down: range(2, -1, -1) gives 2, 1, 0. The stop is -1, not 0, because a range stops before its stop, and 0 is the last position we want.

The trace splits a line with messy spacing, walks the words from the end, and joins them back with -. Guess what the last line prints.

▶1line = " load  the table"
2words = line.split()
3for i in range(len(words) - 1, -1, -1):
4    print(words[i])
5print("-".join(words))

(nothing printed yet)

Now put split, a list and join together in the right order, to turn "extract transform load" into its initials, "ETL".

Reversing the order of the words takes all three moves: split to get the words, walk them from the last to the first while collecting them in a list, and join once with one space.

The problem's speed test, with 300,000 words, is immutability in action. Putting each word in front of a growing string copies that string every time. Collecting a list and joining once copies each character once.

So far: strings never change, so build new ones from a list of pieces and join once. split() gives the words, join glues them back, and ord(c) - ord("a") turns a lowercase letter into a number from 0 to 25.