Strings

An array of characters with one extra rule in most languages: you cannot change it. That rule quietly turns innocent-looking loops into O(n²) code.

Class 11 to 12beginner30 min4 lessons

By the end you will be able to

Describe a string as an indexed sequence of characters
Explain what immutability costs when building a string in a loop
Reach for the two-pointer pattern on reverse and palindrome problems
Distinguish a character from a byte and from a code point

Finish first

Arrays

Cost at a glance

access: O(1)
length: O(1)
concatenate: O(n + m)
slice: O(k)
naiveSearch: O(n·m)

Topic contents

Lesson 1 of 4

An array you cannot edit

A string is an array of characters, so everything you know about arrays applies: index access is O(1), scanning is O(n), and the characters sit side by side in memory. What changes is that in JavaScript, Python, Java and C#, strings are immutable. There is no operation that edits a string in place; every operation that appears to change one actually builds a new string and leaves the original untouched.

That is a deliberate trade. Immutability makes strings safe to share, cheap to compare for equality by reference, and usable as dictionary keys without fear that someone mutates them behind your back. It also means the cost of a change is the cost of copying.

Continue

Lesson 2 of 4

The accidental O(n²)

Concatenating inside a loop is the most common performance bug in beginner code. `result += word` looks like appending, but because the string cannot be edited, each iteration allocates a fresh string and copies everything accumulated so far. Copy 1 character, then 2, then 3, and by the end you have copied n(n+1)/2 characters to build a string of length n.

The fix is to stop building intermediate strings. Collect the pieces in an array and join once at the end, which copies each character exactly once for O(n) total. Java calls the same idea StringBuilder; Python's canonical form is `''.join(parts)`. The lesson generalises: when an immutable value is being rebuilt in a loop, look for the batched version of the operation.

Watch it happen

Building a string, two ways

Watch the gap open up as the input grows. Both lines do the same job; only one of them copies the work it already did.

join once4
+= in a loop16

1 / 5

n = 4

With 4 items: join once ≈ 4 · += in a loop ≈ 16. The flat lines barely notice; the steep ones are already unusable.

Continue

Lesson 3 of 4

Two pointers, one pass

A large family of string questions is solved by walking two indexes towards each other from the ends. Is this a palindrome? Compare first with last, step both inwards, stop on the first mismatch. Reverse in place (in a language where you can)? Swap the pair and step inwards. Both are O(n) time and O(1) extra space, and neither needs a second copy of the string.

The pattern is worth naming because it replaces the instinct to build reversed copies and compare them. Comparing a string with its reverse also answers the palindrome question, but it allocates a whole second string to do it. Same complexity class, twice the memory, and it stops looking clever the moment the input is large.

Continue

Lesson 4 of 4

Characters are not bytes

Text is where the tidy model breaks. `"café".length` may be 4 or 5 depending on how the accent was encoded, and an emoji such as 👍 counts as 2 in JavaScript because the language indexes UTF-16 code units, not human-visible characters. Slice through the middle of one of those pairs and you get a broken character back.

You do not need to master Unicode to write correct code, but you do need one habit: never assume one index equals one character when the text can come from a user. Iterate with the language's text-aware iterator (`for...of` in JavaScript, which walks code points) and treat `.length` as a count of storage units rather than of letters.

Continue

Worked examples

Read the code, then change it

Copy any example into the playground and break it on purpose. That is the fastest way to learn what each line is holding up.

Concatenation versus joinJavaScript

const words = Array.from({ length: 20000 }, (_, i) => 'w' + i);

// O(n^2): every += copies everything built so far.
let slow = '';
const startSlow = performance.now();
for (const word of words) slow += word;
const slowMs = performance.now() - startSlow;

// O(n): each character is copied exactly once.
const startFast = performance.now();
const fast = words.join('');
const fastMs = performance.now() - startFast;

console.log('same result:', slow === fast);
console.log('+= took', slowMs.toFixed(1), 'ms');
console.log('join took', fastMs.toFixed(1), 'ms');

Palindrome with two pointersJavaScript

function isPalindrome(text) {
  const clean = text.toLowerCase().replace(/[^a-z0-9]/g, '');
  let left = 0;
  let right = clean.length - 1;
  while (left < right) {
    if (clean[left] !== clean[right]) return false; // stop at the first mismatch
    left += 1;
    right -= 1;
  }
  return true;
}

console.log(isPalindrome('A man, a plan, a canal: Panama')); // true
console.log(isPalindrome('codexlab'));                       // false

// Characters are not units:
console.log('👍'.length);            // 2, one emoji, two UTF-16 units
console.log([...'👍'].length);       // 1, code points

Practice

Work these out yourself

No answer key here on purpose: these are the questions worth thinking through before you move on. Open one and work it out.

0/4 attempted

Finished this topic?

0 of 4 lessons marked done. Marking the topic complete ticks the rest.

An array you cannot edit

The accidental O(n²)

Two pointers, one pass

Characters are not bytes

Read the code, then change it

Work these out yourself

Check your understanding

Finished this topic?