Strings

Your script writes a sales report one line at a time: report += line, ten thousand times. On a small test it finishes instantly. On a full year of data it takes noticeably longer than it should, and the extra time grows much faster than the number of lines.

The code is not wrong. It is paying for one fact that is easy to forget: you cannot change a string. Every += may build a brand new one.

#A string is an array of characters

Underneath, a string is an array of characters stored side by side. Everything you learned about arrays carries over. s[3] is O(1). s.length in JavaScript and len(s) in Python are O(1), because the length is stored. Looping over every character is O(n).

Each character is stored as a number, its character code. The lowercase letters a to z have the codes 97 to 122, in order. So subtracting the code of a turns any lowercase letter into a position from 0 to 25: c is 99 − 97 = 2. You will use that trick in a moment.

#You cannot change a string in place

Strings in JavaScript and Python are immutable. Once made, they never change. s[0] = "J" does nothing in JavaScript (or throws, in strict mode) and raises an error in Python. Methods like toUpperCase(), replace() and slicing do not edit the string. They return a new one.

That is why report += line can be slow. The old report cannot grow, so the language may allocate a new string and copy the old report plus the new line into it. The first line is copied once, the second line twice, the third three times, and so on.

For n pieces that is 1 + 2 + … + n, about n²/2 copies: O(n²). Ten thousand lines means around 50 million line copies where ten thousand would do.

The fix is to collect the pieces in an array, which grows cheaply at the end, and glue them together once at the very end. join measures the total length first and copies each piece exactly once.

function buildReport(sales) {
  const lines = [];
  for (const sale of sales) {
    lines.push(`${sale.item}: ${sale.amount}`); // cheap append to an array
  }
  return lines.join("\n"); // one copy of everything, at the end
}
 
buildReport([{ item: "tea", amount: 4 }, { item: "cake", amount: 7 }]);
// "tea: 4\ncake: 7"

def build_report(sales):
    lines = []
    for sale in sales:
        lines.append(f"{sale['item']}: {sale['amount']}")  # cheap append to a list
    return "\n".join(lines)  # one copy of everything, at the end
 
build_report([{"item": "tea", "amount": 4}, {"item": "cake", "amount": 7}])
# "tea: 4\ncake: 7"

To be fair to +=: modern JavaScript engines, and CPython in simple cases, often avoid the full copy behind the scenes. You cannot count on it, and the rule costs nothing to follow. In a loop, build a list and join it.

#Counting letters with 26 boxes

Many string problems come down to "which characters appear, and how often?" Take this one: are two words anagrams, made of exactly the same letters? tea and eat are. tea and tee are not.

You could sort both words and compare, but there is a simpler way when the words use only lowercase letters. Keep 26 counters, one per letter. Walk the first word and add 1 for each letter. Walk the second word and subtract 1. If they are anagrams, every counter ends at 0. In the tracer only the counters for a, e and t are shown; the other 23 stay at 0 throughout.

if lengths differ: return falsecounts = 26 zerosfor ch in first: counts[ch - 'a'] += 1for ch in second: counts[ch - 'a'] -= 1return every count is 0

With tea and tee, the a counter would end at 1 and the e counter at −1. Any counter that is not 0 means some letter appears more often in one word than the other.

// Assumes both words use only lowercase a to z.
function isAnagram(first, second) {
  if (first.length !== second.length) return false;
  const counts = new Array(26).fill(0);
  const A = "a".charCodeAt(0); // 97
  for (const ch of first) counts[ch.charCodeAt(0) - A]++;
  for (const ch of second) counts[ch.charCodeAt(0) - A]--;
  return counts.every((c) => c === 0);
}
 
isAnagram("tea", "eat"); // true
isAnagram("tea", "tee"); // false

# Assumes both words use only lowercase a to z.
def is_anagram(first, second):
    if len(first) != len(second):
        return False
    counts = [0] * 26
    for ch in first:
        counts[ord(ch) - ord("a")] += 1
    for ch in second:
        counts[ord(ch) - ord("a")] -= 1
    return all(c == 0 for c in counts)
 
is_anagram("tea", "eat")  # True
is_anagram("tea", "tee")  # False

The 26 counters are O(1) space because their number never changes with the input. Sorting both words would also work, but costs O(n log n).

#Common mistakes

#Check yourself

#What to practise next

The 26 counters only work because the alphabet is small and known in advance. To count words, user IDs or anything else, you need a structure that turns any key into a box number. That is a hash table.