Chapter 03 — Strings
Chapter 03 — Strings
Hey everyone! Welcome back to Namaste DSA!
Strings are everywhere — names, messages, DNA sequences, file paths. Under the hood, a string is just an array of characters. But JavaScript adds one critical twist that trips up beginners: strings are immutable. Understanding that changes how you write efficient string code.
What we will cover:
- Strings as arrays of characters
- Immutability — and why it makes loops slow
- Character codes & ASCII
- Reversing a string
- Palindrome check
- Anagram check (frequency counting)
- Substring vs subsequence
- Interview Questions
1. A String is an Array of Characters
┌─────────────────────────────────────────────────────────────┐ │ STRING = "HELLO" │ ├─────────────────────────────────────────────────────────────┤ │ Index: 0 1 2 3 4 │ │ ┌────┐┌────┐┌────┐┌────┐┌────┐ │ │ │ H ││ E ││ L ││ L ││ O │ │ │ └────┘└────┘└────┘└────┘└────┘ │ │ │ │ str[0] = "H" str.length = 5 │ └─────────────────────────────────────────────────────────────┘
You can read any character by index in O(1), just like an array: "HELLO"[1] gives "E".
2. Immutability — The Big Twist
In JavaScript you cannot change a character in place. This silently fails:
let s = "cat"; s[0] = "b"; // ❌ does nothing! console.log(s); // still "cat"
Every "change" actually creates a brand new string. This has a huge performance consequence — building a string in a loop with += is secretly O(n²):
┌─────────────────────────────────────────────────────────────┐ │ WHY "result += char" IN A LOOP IS O(n²) │ ├─────────────────────────────────────────────────────────────┤ │ Each += creates a NEW string by copying the old one. │ │ │ │ step 1: copy 1 char → "a" │ │ step 2: copy 2 chars → "ab" │ │ step 3: copy 3 chars → "abc" │ │ ... │ │ 1 + 2 + 3 + ... + n = n(n+1)/2 → O(n²) total copies! │ └─────────────────────────────────────────────────────────────┘
The fix: push characters into an array (mutable, O(1) push), then join("") once at the end — total O(n).
// SLOW — O(n²)
let result = "";
for (const c of arr) result += c;
// FAST — O(n)
const parts = [];
for (const c of arr) parts.push(c);
const result = parts.join("");
3. Character Codes & ASCII
Every character maps to a number. Useful for math on letters.
"A".charCodeAt(0) → 65 "a".charCodeAt(0) → 97 "0".charCodeAt(0) → 48 String.fromCharCode(66) → "B" // Index of a lowercase letter in the alphabet (0-25): c.charCodeAt(0) - 97 // "a"→0, "b"→1, ... "z"→25
This trick lets us use a fixed 26-slot array as a frequency counter for lowercase letters — pure O(1) space.
4. Reversing a String
// Simplest (uses array): O(n)
function reverse(s) {
return s.split("").reverse().join("");
}
// Two-pointer on a char array (shows the mechanics):
function reverseManual(s) {
const chars = s.split("");
let l = 0, r = chars.length - 1;
while (l < r) {
[chars[l], chars[r]] = [chars[r], chars[l]];
l++; r--;
}
return chars.join("");
}
5. Palindrome Check
A palindrome reads the same forwards and backwards ("madam", "racecar"). Use two pointers — O(n) time, O(1) space.
function isPalindrome(s) {
let l = 0, r = s.length - 1;
while (l < r) {
if (s[l] !== s[r]) return false;
l++; r--;
}
return true;
}
HAND TRACE: "racecar" l=0(r) r=6(r) ✔ l=1(a) r=5(a) ✔ l=2(c) r=4(c) ✔ l=3 r=3 → l not < r → STOP → true ✔
6. Anagram Check — Frequency Counting
Two strings are anagrams if they contain the same letters in any order ("listen" / "silent"). Count letter frequencies and compare.
function isAnagram(a, b) {
if (a.length !== b.length) return false;
const count = new Array(26).fill(0);
for (let i = 0; i < a.length; i++) {
count[a.charCodeAt(i) - 97]++; // add for a
count[b.charCodeAt(i) - 97]--; // subtract for b
}
return count.every(c => c === 0); // all balanced?
}
// Time O(n), Space O(1) — the 26-slot array is constant.
7. Substring vs Subsequence — Don't Confuse Them!
┌─────────────────────────────────────────────────────────────┐ │ String: "ABCDE" │ ├─────────────────────────────────────────────────────────────┤ │ SUBSTRING → must be CONTIGUOUS │ │ "BCD" ✔ "ACE" ✗ (gaps) │ │ │ │ SUBSEQUENCE → keep ORDER, gaps allowed │ │ "ACE" ✔ "BCD" ✔ "AED" ✗ (wrong order) │ └─────────────────────────────────────────────────────────────┘
This distinction matters constantly — "longest substring without repeats" (sliding window, Chapter 07) vs "longest common subsequence" (DP, Chapter 22).
Interview Questions — Quick Fire!
Q: Are strings mutable in JavaScript?
"No, JavaScript strings are immutable. You can't change a character in place — any operation that looks like a change actually creates a new string. That's why building a string with += in a loop is O(n²); you should push to an array and join once instead."
Q: Why is concatenating strings in a loop slow?
"Because each concatenation creates a new string by copying all existing characters. Over n iterations that's 1+2+...+n copies, which is O(n²). Collecting parts in an array and calling join('') at the end is O(n)."
Q: How do you check if two strings are anagrams?
"If lengths differ they can't be anagrams. Otherwise count each letter — increment for the first string, decrement for the second using a 26-slot array — and check everything is zero. That's O(n) time and O(1) space. Alternatively, sort both and compare, which is O(n log n)."
Q: What's the difference between a substring and a subsequence?
"A substring is a contiguous block of characters. A subsequence keeps the original order but allows gaps. For 'ABCDE', 'BCD' is a substring, while 'ACE' is a subsequence but not a substring."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| String | Array of characters; index access O(1). |
| Immutable | Can't change in place; += in a loop is O(n²). |
| Build fast | Push to array, join once → O(n). |
| charCodeAt - 97 | Map a-z to 0-25 for frequency arrays. |
| Palindrome | Two pointers, O(n) time O(1) space. |
| Anagram | Frequency count, O(n). |
| Substring vs subsequence | Contiguous vs ordered-with-gaps. |
What's Next?
Chapter 04 unlocks the most powerful tool in interviews: Hashing. We'll see how Maps and Sets give O(1) lookups and how the "have I seen this before?" pattern solves Two Sum instantly.
Keep coding, keep grinding! See you in the next one!
Post a Comment