String Manipulation & Pattern Matching

0/14 in this phase0/57 across the roadmap

📖 Concept

Strings are immutable sequences of characters. In DSA, string problems are extremely common in interviews and often combine with arrays, hash maps, and sliding windows.

Key facts:

Strings are immutable in JS/TS — every modification creates a new string
String concatenation in a loop is O(n²) — use array.join() instead
Characters are accessed like arrays: str[i] or str.charAt(i)
Strings are compared lexicographically (dictionary order)

Common string patterns for interviews:

Two pointers — palindrome check, reverse
Hash map/frequency count — anagram check, character counting
Sliding window — longest substring without repeats
String building — use array + join, not string concatenation

Internal representation:

JavaScript uses UTF-16 encoding
Most characters are 2 bytes, but emojis/rare chars are 4 bytes (surrogate pairs)
str.length counts UTF-16 code units, not characters: "😀".length === 2

🏠 Real-world analogy: Strings are like text printed on paper — you can read any character instantly but can't erase or change one. To "modify" it, you photocopy with the change.

💻 Code Example

codeTap to expand ⛶

1// STRING IMMUTABILITY
2let str = "Hello";
3str[0] = "J";         // Silently fails! Strings are immutable
4console.log(str);      // Still "Hello"
5str = "J" + str.slice(1); // Create NEW string: "Jello"
6
7// O(n²) BAD — string concatenation in loop
8function buildStringBad(n: number): string {
9  let result = "";
10  for (let i = 0; i < n; i++) {
11    result += i.toString(); // Creates new string each time!
12  }
13  return result; // O(n²) total!
14}
15
16// O(n) GOOD — array + join
17function buildStringGood(n: number): string {
18  const parts: string[] = [];
19  for (let i = 0; i < n; i++) {
20    parts.push(i.toString());
21  }
22  return parts.join(""); // O(n) total
23}
24
25// FREQUENCY COUNT — Foundation for many string problems
26function charFrequency(str: string): Map<string, number> {
27  const freq = new Map<string, number>();
28  for (const char of str) {
29    freq.set(char, (freq.get(char) || 0) + 1);
30  }
31  return freq;
32}
33
34// IS ANAGRAM — O(n) using frequency count
35function isAnagram(s: string, t: string): boolean {
36  if (s.length !== t.length) return false;
37  const count = new Map<string, number>();
38  for (const c of s) count.set(c, (count.get(c) || 0) + 1);
39  for (const c of t) {
40    const val = count.get(c);
41    if (!val) return false;
42    count.set(c, val - 1);
43  }
44  return true;
45}
46
47// IS PALINDROME — Two pointers O(n) time, O(1) space
48function isPalindrome(s: string): boolean {
49  let l = 0, r = s.length - 1;
50  while (l < r) {
51    if (s[l] !== s[r]) return false;
52    l++; r--;
53  }
54  return true;
55}
56
57// LONGEST SUBSTRING WITHOUT REPEATING — Sliding window
58function lengthOfLongestSubstring(s: string): number {
59  const seen = new Map<string, number>();
60  let maxLen = 0, start = 0;
61  for (let end = 0; end < s.length; end++) {
62    if (seen.has(s[end]) && seen.get(s[end])! >= start) {
63      start = seen.get(s[end])! + 1;
64    }
65    seen.set(s[end], end);
66    maxLen = Math.max(maxLen, end - start + 1);
67  }
68  return maxLen;
69}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

Reverse a string without using built-in reverse
Check if two strings are anagrams of each other
Find the first non-repeating character in a string
Check if a string is a valid palindrome (ignoring non-alphanumeric)
Longest common prefix of an array of strings
String compression: "aabcccccaaa" → "a2b1c5a3"
Longest substring without repeating characters
Check if string s can be formed by repeating a pattern
Minimum window substring containing all target characters
Longest palindromic substring

⚠️ Common Mistakes

String concatenation in loops — O(n²) due to immutability; use Array.push + join
Forgetting strings are immutable — str[i] = 'x' silently fails
Not handling Unicode properly — '😀'.length is 2, not 1; use Array.from() or for...of
Using == for string comparison when case matters — 'Hello' !== 'hello'
Assuming indexOf returns boolean — it returns -1 for not found; use includes() instead

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for String Manipulation & Pattern Matching

Was this topic helpful?

← PreviousArrays — Deep Dive & Internal Implementation Next →Singly Linked Lists — Build from Scratch