Algorithms from zero
Strings are arrays
You know arrays: a row of boxes, indexed, contiguous. A string is a row of characters. Algorithmically, it is an array. You can jump to any character by index in O(1) time. But strings are different in one critical way: they are immutable. Once created, you cannot change a single character. This immutability creates a trap: building a string by repeating concatenation in a loop is secretly O(n²).
After this lesson you can treat a string as an array of characters, explain why strings are immutable, recognize the O(n²) concatenation trap and how to fix it, apply Unit 02 patterns (two pointers, sliding window) to strings, understand character codes and comparisons, and solve classic string problems.
A string is a sequence of characters stored contiguously in memory. In JavaScript (and many other languages), a string is read-only—immutable. Once created, you cannot modify a single character.
Why treat strings as arrays?
Like an array, a string has:
- Zero-based indexing:
s[0]is the first character,s[1]is the second, etc. - O(1) character access: Jump to any index and read the character in constant time.
- Known length:
s.lengthis the number of characters. - Traversal: Loop through with
for (let i = 0; i < s.length; i++), exactly like an array.
This means every Unit 02 pattern (two pointers, sliding window, traversal) applies to strings too.
The immutability trap: O(n²) concatenation
Because strings are immutable, each += operation creates a new string and copies all characters from the old string into it.
// ❌ This is O(n²)
let result = "";
for (let i = 0; i < 1000; i++) {
result += "x"; // Each += creates a new string and copies result into it
}Why O(n²)? Trace it:
- Iteration 1: copy 0 chars, write 1 char. Work = 1.
- Iteration 2: copy 1 char, write 1 char. Work = 2.
- Iteration 3: copy 2 chars, write 1 char. Work = 3.
- …
- Iteration n: copy (n-1) chars, write 1 char. Work = n.
Total work = 1 + 2 + 3 + … + n = O(n²).
For 1000 iterations, you do ~500,000 character copies. For 10,000 iterations, ~50 million. The trap hides in innocent-looking code.
The fix: collect into an array, then join
// ✅ This is O(n)
const result = [];
for (let i = 0; i < 1000; i++) {
result.push("x"); // Array push is O(1) amortized
}
const str = result.join(""); // One join pass is O(n)Why O(n)? Push is O(1) amortized (no copying). The join walks through the array once and builds the final string in a single pass.
Characters and character codes
Each character has an associated numeric code. In JavaScript, use charCodeAt(i) to get the code and String.fromCharCode(code) to build a character from its code.
'a'.charCodeAt(0); // 97
'z'.charCodeAt(0); // 122
String.fromCharCode(97); // 'a'Character codes are ordered: 'a' = 97, 'b' = 98, …, 'z' = 122. When you compare characters with < or >, you compare their codes. This is why 'a' < 'b' is true.
Unit 02 patterns on strings
All the techniques you learned now work on strings:
- Two pointers: Check if a string is a palindrome (compare opposite ends).
- Sliding window: Find the longest substring with unique characters.
- Traversal: Count how many times each character appears, scan for a pattern.
- In-place modification: Build a new string with specific characters.
Let us code classic string problems:
1. Palindrome check with two pointers (opposite-ends):
function isPalindrome(s) {
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) {
return false; // Mismatch: not a palindrome
}
left++;
right--;
}
return true; // All pairs matched
}2. Character count (traversal + accumulator pattern):
function charCount(s) {
const count = {};
for (let i = 0; i < s.length; i++) {
const char = s[i];
count[char] = (count[char] || 0) + 1;
}
return count;
}3. Build string efficiently (array collect + join):
function repeatChar(ch, n) {
const chars = [];
for (let i = 0; i < n; i++) {
chars.push(ch);
}
return chars.join(""); // O(n) total
}Try running these:
Watch the palindrome check step by step on “racecar”:
1
function isPalindrome(s) {
2
let left = 0, right = s.length - 1;
3
while (left < right) {
4
if (s[left] !== s[right]) return false;
5
left++;
6
right--;
7
}
8
return true;
9
}
Now trace the concatenation trap vs. the efficient fix:
For 5 iterations building “xxxxx”, the naive += way:
- Iter 1: copy "", add “x” → “x” (work = 1)
- Iter 2: copy “x”, add “x” → “xx” (work = 2)
- Iter 3: copy “xx”, add “x” → “xxx” (work = 3)
- Iter 4: copy “xxx”, add “x” → “xxxx” (work = 4)
- Iter 5: copy “xxxx”, add “x” → “xxxxx” (work = 5)
Total: 1+2+3+4+5 = 15 character copies.
Efficient way: push 5 times (5 × O(1) = O(5)), then join once (O(5) to build string). Total: ~10 operations.
String operations and their costs:
| Operation | Example | Time |
|---|---|---|
| Access character by index | s[5] | O(1) |
| Get length | s.length | O(1) |
| Check palindrome (two pointers) | isPalindrome(s) | O(n) |
| Count characters (traversal) | charCount(s) | O(n) |
Build by += in loop | result += s[i] repeated | O(n²) ❌ |
| Build by array + join | arr.push(); arr.join() | O(n) ✅ |
| Sliding window substring | longestUnique(s) | O(n) |
The concatenation trap—why it matters:
For a 1000-character string built by += in a loop, you do ~500,000 character copies. For 10,000 characters, ~50 million. The code looks simple, but the hidden cost is quadratic.
Using array + join is always better when building strings from parts.
Why is string indexing (e.g., s[5]) O(1) if strings are immutable?
What is the time complexity of this code? let result = ''; for (let i = 0; i < 1000; i++) { result += 'x'; }
How do you fix the O(n²) concatenation trap?
Check if 'level' is a palindrome using two pointers. What will isPalindrome('level') return? (1 = true, 0 = false)
If you count characters in a string using a loop (charCount), what is the time complexity?
Common mistake
Building a string with += in a loop. You write let result = ""; for (let i = 0; i < n; i++) { result += someStr[i]; } and think it is O(n). But each += is actually creating a new string and copying the old one into it. You end up with O(n²) work—the same trap that catches people building lists in many languages. The fix: always use an array and join.
Edge cases
Empty and single-character strings. A string of length 0 behaves like a length-0 array: indexing is out of bounds, loops never run. A string of length 1 has one character at index 0; two-pointer loops exit immediately (left < right is 0 < 0 = false). Both edge cases are handled correctly by the algorithms.
A string is immutable in JavaScript, so you cannot change a character in place. How does this immutability lead to the O(n²) concatenation trap?
A string is an array of characters—it is indexed, contiguous, and you can access any character in O(1) time.
Key facts:
-
Strings are immutable: Once created, you cannot change a character in place. Each modification creates a new string.
-
Character indexing is O(1): Like arrays, jump to
s[i]directly without scanning. -
The concatenation trap is O(n²): Each
+=copies the entire string so far. Building a string character-by-character takes O(n²) work. -
The fix is array + join: Push characters into an array (O(1) amortized each), then join once (O(n)). Total: O(n).
-
Unit 02 patterns work on strings: Two pointers for palindromes, sliding window for substrings, traversal for character counting.
-
Characters are ordered by code:
'a'<'b'< … <'z'. UsecharCodeAt(i)to get the numeric code.
You now have the full Unit 02 toolkit: arrays, traversal, two pointers, sliding window, prefix sums, in-place modification, and strings as arrays. Next, you will learn how to sort data and search efficiently in sorted arrays.