DSAStrings

Strings

A string is a sequence of characters. Under the hood it is just an indexed array of characters stored in contiguous memory — and that mental model unlocks every string algorithm you will ever write.

Strings as Character Arrays

In C, a string literally is a char[] terminated by a null byte '\0'. JavaScript raises the abstraction level, but the indexing behaviour is identical:

JS
const s = "hello";

// Index like an array
console.log(s[0]); // 'h'
console.log(s[4]); // 'o'

// Classic for-loop iteration
for (let i = 0; i < s.length; i++) {
  process(s[i]);
}

// for...of iterates Unicode code points (safer for emoji)
for (const ch of s) {
  process(ch);
}

// When you need to mutate: convert to array, edit, join back
const chars = s.split('');
chars[0] = 'H';
console.log(chars.join('')); // 'Hello'
Immutability in JavaScript

JavaScript strings are immutable — you cannot change a character in place. Every operation that appears to "modify" a string actually returns a new string. This has a critical performance consequence.

JS
const s = "hello";

// Does NOT work — assignment is silently ignored
s[0] = 'H';
console.log(s); // still 'hello'

// Correct: build a new string
const result = 'H' + s.slice(1);
console.log(result); // 'Hello'

// ❌ Performance trap — O(n²) in a loop
let bad = '';
for (let i = 0; i < 100_000; i++) {
  bad += 'x'; // copies the entire string every iteration
}

// ✅ Correct — O(n) with array buffer
const parts = [];
for (let i = 0; i < 100_000; i++) {
  parts.push('x');
}
const good = parts.join(''); // single allocation
Warning
Never concatenate strings with += inside a loop. Each += copies the entire accumulated string, making the loop O(n²). Always collect characters in an array and call join('') once at the end.
Essential Built-in Operations

Method

What it does

Complexity

s.length

Number of UTF-16 code units

O(1)

s[i] / s.charAt(i)

Character at index i

O(1)

s.slice(start, end)

Substring [start, end)

O(end-start)

s.indexOf(sub)

First index of sub, or -1

O(n·m) naive

s.includes(sub)

Boolean membership test

O(n·m) naive

s.split(sep)

Split into array

O(n)

arr.join(sep)

Join array into string

O(n)

s.replace(pat, rep)

Replace first match

O(n)

s.replaceAll(pat, rep)

Replace all matches

O(n)

s.toLowerCase()

All chars to lowercase

O(n)

s.trim()

Remove leading/trailing whitespace

O(n)

s.startsWith(sub)

Does string begin with sub?

O(m)

s.repeat(n)

Concatenate n copies

O(n·len)

s.padStart(len, ch)

Pad left to length len

O(len)

JS
const s = "  Hello, World!  ";

// Trim whitespace, change case
console.log(s.trim().toLowerCase()); // 'hello, world!'

// slice — end index is exclusive, negatives count from end
console.log(s.trim().slice(0, 5));   // 'Hello'
console.log(s.trim().slice(-6, -1)); // 'World'

// indexOf / includes
console.log(s.indexOf('World')); // 9
console.log(s.indexOf('xyz'));   // -1
console.log(s.includes('Hello')); // true

// split / join
console.log('a,b,c'.split(','));  // ['a', 'b', 'c']
console.log('hello'.split(''));   // ['h','e','l','l','o']

// replace
console.log('aabbcc'.replace('b', 'X'));    // 'aaXbcc'  (first only)
console.log('aabbcc'.replaceAll('b', 'X')); // 'aaXXcc'  (all)

// padStart — useful for zero-padding numbers
console.log(String(7).padStart(3, '0')); // '007'
Character Frequency with Map

Counting how often each character appears is the foundation of anagram detection, sliding window problems, and many more. You have three options ranked by speed:

JS
// Option 1 — Map (works for any character set)
function charFreq(s) {
  const freq = new Map();
  for (const ch of s) {
    freq.set(ch, (freq.get(ch) ?? 0) + 1);
  }
  return freq;
}

// Option 2 — Plain object (slightly faster due to V8 optimisations)
function charFreqObj(s) {
  const freq = {};
  for (const ch of s) {
    freq[ch] = (freq[ch] || 0) + 1;
  }
  return freq;
}

// Option 3 — Fixed array (fastest; only for lowercase a-z)
function charFreqArray(s) {
  const freq = new Array(26).fill(0);
  const a = 'a'.charCodeAt(0);
  for (const ch of s) {
    freq[ch.charCodeAt(0) - a]++;
  }
  return freq;
}

// Classic use case: anagram check
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const freq = new Array(26).fill(0);
  const a = 'a'.charCodeAt(0);
  for (let i = 0; i < s.length; i++) {
    freq[s.charCodeAt(i) - a]++;
    freq[t.charCodeAt(i) - a]--;
  }
  return freq.every(n => n === 0);
}

console.log(isAnagram('listen', 'silent')); // true
console.log(isAnagram('hello',  'world'));  // false
Note
For lowercase-only problems use a 26-element array. Index a character with ch.charCodeAt(0) - 97 (the ASCII code of 'a'). This eliminates Map overhead and cache misses.
ASCII and Unicode

Every character has a numeric code point. ASCII covers values 0–127:

  • Digits 09 → 48–57
  • Uppercase AZ → 65–90
  • Lowercase az → 97–122
  • The gap between upper and lowercase is exactly 32

JavaScript strings are UTF-16. Characters outside the Basic Multilingual Plane (most emoji, rare CJK) occupy two UTF-16 code units called a surrogate pair. str.length counts code units — not visible characters — so be careful with emoji.

JS
// charCodeAt / fromCharCode
console.log('A'.charCodeAt(0));        // 65
console.log('a'.charCodeAt(0));        // 97  (65 + 32)
console.log(String.fromCharCode(65));  // 'A'

// 0-based alphabet index
const idx = ch => ch.charCodeAt(0) - 'a'.charCodeAt(0);
console.log(idx('a')); // 0
console.log(idx('z')); // 25

// Emoji / surrogate pair trap
const emoji = '😀';
console.log(emoji.length);       // 2  ← code units, not characters!
console.log([...emoji].length);  // 1  ← spread uses code points (correct)

// Safe iteration for any Unicode text
for (const ch of '😀Hi') {
  console.log(ch); // '😀', 'H', 'i'
}

// Toggle case using the 32-bit gap
function toggleCase(ch) {
  const code = ch.charCodeAt(0);
  if (code >= 65 && code <= 90)  return String.fromCharCode(code + 32); // upper→lower
  if (code >= 97 && code <= 122) return String.fromCharCode(code - 32); // lower→upper
  return ch;
}
Common Interview Patterns at a Glance

Pattern

When to reach for it

Signature problems

Two Pointers

Symmetric reasoning, in-place reversal, palindrome

Reverse String, Valid Palindrome

Sliding Window

Longest/shortest substrings with a constraint

Longest Substring Without Repeating Chars

Frequency Map

Counting chars, comparing multisets

Valid Anagram, Group Anagrams

Stack

Matching brackets, nested structures

Valid Parentheses, Decode String

DP on strings

Subsequences, edit operations, alignment

LCS, Edit Distance, Wildcard Matching

Pattern Matching

Substring search in linear time

KMP, Rabin-Karp, strStr

Checklist Before You Code
  1. What is the character set? Lowercase only (use 26-array)? Full ASCII? Unicode?

  2. Are inputs already cleaned — trimmed, lowercased?

  3. What are the edge cases? Empty string, single character, all same characters?

  4. Can a two-pointer approach replace a nested loop?

  5. Am I building a result string? If so, use an array + join at the end.

  6. Does the problem ask about substrings? Think sliding window first.

Tip
Most string problems reduce to: scan once, maintain a frequency map or a two-pointer window, check a condition. If you have a nested loop, ask whether a Map or sliding window can collapse it to O(n).
Practice Problems
  • LeetCode 344 — Reverse String (in-place two pointers)

  • LeetCode 242 — Valid Anagram (frequency array)

  • LeetCode 387 — First Unique Character in a String (frequency map)

  • LeetCode 125 — Valid Palindrome (two pointers + clean)

  • LeetCode 14 — Longest Common Prefix (vertical scan)

  • LeetCode 49 — Group Anagrams (sorted key map)

  • LeetCode 3 — Longest Substring Without Repeating Characters (sliding window)