String Algorithms

Algorithm	Preprocessing	Matching	Space	Best For
Naive	`O(1)`	`O(n×m)`	`O(1)`	Short patterns, teaching
KMP	`O(m)`	`O(n)`	`O(m)`	Single pattern, no backtracking
Rabin-Karp	`O(m)`	`O(n+m)` avg	`O(1)`	Multiple patterns, plagiarism detection
Boyer-Moore	`O(m+σ)`	`O(n/m)` best	`O(m+σ)`	Large texts, text editors (σ = alphabet size)
Z Algorithm	`O(m)`	`O(n+m)`	`O(n+m)`	Pattern matching variants
Aho-Corasick	`O(∑m)`	`O(n+k)`	`O(∑m)`	Multiple patterns simultaneously (k = matches)
Manacher	-	`O(n)`	`O(n)`	Longest palindromic substring
Suffix Array	`O(n log n)`	`O(m log n)`	`O(n)`	Multiple searches, genome analysis

1. Naive Pattern Matching Brute Force

Aspect	Description	Characteristic
Algorithm	Try all possible alignments of pattern in text	Check character by character at each position
Time Complexity	`O((n-m+1) × m) = O(n×m)`	Worst when many partial matches
Best Case	`O(n)` when first character never matches	Early mismatch eliminates position quickly
Worst Case	Pattern: "AAA", Text: "AAAAAAA"	Maximum comparisons at each position
Space Complexity	`O(1)`	No extra data structures needed
Use Cases	Very short patterns, educational purposes	Not practical for production systems

Example: Naive Pattern Matching

function naivePatternMatch(text, pattern) {
    const n = text.length;
    const m = pattern.length;
    const matches = [];
    
    // Try each possible starting position
    for (let i = 0; i <= n - m; i++) {
        let j = 0;
        
        // Check if pattern matches at position i
        while (j < m && text[i + j] === pattern[j]) {
            j++;
        }
        
        // If full pattern matched
        if (j === m) {
            matches.push(i);
        }
    }
    
    return matches;
}

console.log(naivePatternMatch("AABAACAADAABAABA", "AABA"));
// Output: [0, 9, 12] - All occurrences found

console.log(naivePatternMatch("ABCDEFGHIJ", "DEF"));
// Output: [3]

// Time: O(n×m) worst case
// Example: Pattern "AAA" in "AAAAAAA" requires many comparisons

2. KMP Algorithm Partial Match Table

Concept	Description	Advantage
LPS Array	Longest Proper Prefix which is also Suffix	Avoid re-checking matched characters
No Backtracking	Text pointer never moves backward	Efficient for streaming data
Preprocessing	Build LPS array from pattern in `O(m)`	One-time cost, reusable for multiple searches
Matching	Use LPS to skip unnecessary comparisons	Linear time `O(n)` guaranteed
Total Complexity	`O(n + m)`	Optimal for single pattern matching
Invented By	Knuth, Morris, Pratt (1977)	First linear-time string matching

Example: KMP Algorithm

function kmpSearch(text, pattern) {
    const n = text.length;
    const m = pattern.length;
    
    // Build LPS (Longest Proper Prefix which is Suffix) array
    const lps = buildLPS(pattern);
    const matches = [];
    
    let i = 0; // Index for text
    let j = 0; // Index for pattern
    
    while (i < n) {
        if (text[i] === pattern[j]) {
            i++;
            j++;
        }
        
        if (j === m) {
            // Pattern found at index (i - j)
            matches.push(i - j);
            j = lps[j - 1]; // Continue searching
        } else if (i < n && text[i] !== pattern[j]) {
            if (j !== 0) {
                // Don't match lps[0..lps[j-1]] characters
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return matches;
}

function buildLPS(pattern) {
    const m = pattern.length;
    const lps = new Array(m).fill(0);
    let len = 0; // Length of previous longest prefix suffix
    let i = 1;
    
    while (i < m) {
        if (pattern[i] === pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len !== 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    return lps;
}

// Example with LPS explanation
const pattern = "ABABCABAB";
const lps = buildLPS(pattern);
console.log("Pattern:", pattern);
console.log("LPS:    ", lps);
// Output: [0, 0, 1, 2, 0, 1, 2, 3, 4]
// Meaning: At index 4 (C), no prefix=suffix
//          At index 8 (B), "ABAB" is both prefix and suffix

console.log(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB"));
// Output: [10] - Pattern found at index 10
// Time: O(n + m), Space: O(m)

Note: KMP never backtracks in the text, making it ideal for streaming data. The LPS array tells us how many characters we can skip when a mismatch occurs, utilizing information from previous matches.

3. Rabin-Karp Rolling Hash Pattern

Feature	Description	Details
Hash Function	Treat string as number in base d	hash = (c₀×d^(m-1) + c₁×d^(m-2) + ... + c_(m-1)) mod q
Rolling Hash	Update hash in `O(1)` by removing/adding character	Remove leading, add trailing, no recalculation
Spurious Hits	Hash match doesn't guarantee string match	Must verify with character comparison
Average Time	`O(n + m)`	With good hash, collisions rare
Worst Time	`O(n×m)`	When all hashes collide (unlikely)
Multiple Patterns	Can search for k patterns in `O(n + k×m)`	Calculate hash for each pattern

Example: Rabin-Karp Algorithm

function rabinKarp(text, pattern) {
    const n = text.length;
    const m = pattern.length;
    const d = 256; // Number of characters in alphabet
    const q = 101; // Prime number for modulo
    
    let patternHash = 0; // Hash value for pattern
    let textHash = 0;    // Hash value for text window
    let h = 1;           // d^(m-1) % q
    const matches = [];
    
    // Calculate h = d^(m-1) % q
    for (let i = 0; i < m - 1; i++) {
        h = (h * d) % q;
    }
    
    // Calculate initial hash values
    for (let i = 0; i < m; i++) {
        patternHash = (d * patternHash + pattern.charCodeAt(i)) % q;
        textHash = (d * textHash + text.charCodeAt(i)) % q;
    }
    
    // Slide pattern over text
    for (let i = 0; i <= n - m; i++) {
        // Check if hash values match
        if (patternHash === textHash) {
            // Verify character by character (avoid spurious hits)
            let match = true;
            for (let j = 0; j < m; j++) {
                if (text[i + j] !== pattern[j]) {
                    match = false;
                    break;
                }
            }
            if (match) matches.push(i);
        }
        
        // Calculate hash for next window (rolling hash)
        if (i < n - m) {
            textHash = (d * (textHash - text.charCodeAt(i) * h) + 
                       text.charCodeAt(i + m)) % q;
            
            // Make sure hash is positive
            if (textHash < 0) textHash += q;
        }
    }
    
    return matches;
}

console.log(rabinKarp("GEEKS FOR GEEKS", "GEEKS"));
// Output: [0, 10]

console.log(rabinKarp("AABAACAADAABAABA", "AABA"));
// Output: [0, 9, 12]

// Average: O(n + m), Worst: O(n×m) but unlikely with good hash

Example: Multiple Pattern Matching with Rabin-Karp

function multiPatternRabinKarp(text, patterns) {
    const d = 256;
    const q = 101;
    const results = {};
    
    // Calculate hashes for all patterns
    const patternHashes = new Map();
    for (const pattern of patterns) {
        let hash = 0;
        for (let i = 0; i < pattern.length; i++) {
            hash = (d * hash + pattern.charCodeAt(i)) % q;
        }
        patternHashes.set(pattern, hash);
        results[pattern] = [];
    }
    
    // Search for each pattern length
    const lengths = [...new Set(patterns.map(p => p.length))];
    
    for (const m of lengths) {
        let h = 1;
        for (let i = 0; i < m - 1; i++) {
            h = (h * d) % q;
        }
        
        let textHash = 0;
        for (let i = 0; i < m; i++) {
            textHash = (d * textHash + text.charCodeAt(i)) % q;
        }
        
        for (let i = 0; i <= text.length - m; i++) {
            // Check all patterns of this length
            for (const pattern of patterns) {
                if (pattern.length === m && 
                    patternHashes.get(pattern) === textHash) {
                    if (text.substring(i, i + m) === pattern) {
                        results[pattern].push(i);
                    }
                }
            }
            
            if (i < text.length - m) {
                textHash = (d * (textHash - text.charCodeAt(i) * h) + 
                           text.charCodeAt(i + m)) % q;
                if (textHash < 0) textHash += q;
            }
        }
    }
    
    return results;
}

const text = "ABABCABCABABABD";
const patterns = ["AB", "ABC", "CAB"];
console.log(multiPatternRabinKarp(text, patterns));
// Output: {AB: [0, 2, 5, 9, 11, 13], ABC: [2, 5], CAB: [4, 7]}

4. Z Algorithm Pattern Matching

Concept	Description	Property
Z Array	Z[i] = length of longest substring starting from i which is also prefix	Z[i] tells how much of string matches from position i
Construction	Build Z array in linear time using [L, R] interval	Maintains rightmost matched segment
Pattern Matching	Concatenate pattern$text and build Z array	Z[i] = m means pattern found at position i
Time Complexity	`O(n + m)`	Linear time, single pass
Space Complexity	`O(n + m)`	Store concatenated string and Z array
Applications	Pattern matching, finding repeating patterns	Simpler than KMP for some problems

Example: Z Algorithm

function buildZArray(str) {
    const n = str.length;
    const z = new Array(n).fill(0);
    
    let l = 0, r = 0;
    
    for (let i = 1; i < n; i++) {
        // If i is outside current [l, r], compute z[i] naively
        if (i > r) {
            l = r = i;
            while (r < n && str[r - l] === str[r]) {
                r++;
            }
            z[i] = r - l;
            r--;
        } else {
            // i is inside [l, r]
            const k = i - l;
            
            // If z[k] < r - i + 1, we can reuse z[k]
            if (z[k] < r - i + 1) {
                z[i] = z[k];
            } else {
                // Start matching from r + 1
                l = i;
                while (r < n && str[r - l] === str[r]) {
                    r++;
                }
                z[i] = r - l;
                r--;
            }
        }
    }
    
    return z;
}

function zAlgorithmSearch(text, pattern) {
    // Concatenate pattern and text with special character
    const concat = pattern + "$" + text;
    const z = buildZArray(concat);
    
    const m = pattern.length;
    const matches = [];
    
    // Find all positions where z[i] equals pattern length
    for (let i = 0; i < z.length; i++) {
        if (z[i] === m) {
            // Found match at position (i - m - 1) in original text
            matches.push(i - m - 1);
        }
    }
    
    return matches;
}

// Demonstrate Z array
const str = "aabcaabxaaaz";
const z = buildZArray(str);
console.log("String:", str);
console.log("Z Array:", z);
// Output: [0, 1, 0, 0, 3, 1, 0, 0, 2, 2, 1, 0]
// Meaning: z[4]=3 means "aab" matches from index 4

console.log(zAlgorithmSearch("ABABDABACDABABCABAB", "ABABCABAB"));
// Output: [10]

// Time: O(n + m), Space: O(n + m)

5. Boyer-Moore String Search

Heuristic	Description	Advantage
Bad Character	Skip alignments based on mismatched character	Jump by max(1, j - last occurrence)
Good Suffix	Use matched suffix to determine shift	Larger shifts when suffix matches elsewhere
Right-to-Left	Compare pattern from right to left	Detect mismatches faster in practice
Best Case	`O(n/m)` - sublinear!	Can skip multiple characters at once
Worst Case	`O(n×m)`	Rare with random text
Practical Use	Fastest for natural language text	Used in grep, text editors

Example: Boyer-Moore (Bad Character Heuristic)

function boyerMooreSearch(text, pattern) {
    const n = text.length;
    const m = pattern.length;
    
    // Build bad character table
    const badChar = buildBadCharTable(pattern);
    const matches = [];
    
    let s = 0; // Shift of pattern with respect to text
    
    while (s <= n - m) {
        let j = m - 1;
        
        // Keep reducing j while characters match
        // Compare from RIGHT to LEFT
        while (j >= 0 && pattern[j] === text[s + j]) {
            j--;
        }
        
        if (j < 0) {
            // Pattern found
            matches.push(s);
            
            // Shift pattern to align next occurrence
            s += (s + m < n) ? m - badChar[text.charCodeAt(s + m)] : 1;
        } else {
            // Shift pattern using bad character heuristic
            const badCharShift = j - badChar[text.charCodeAt(s + j)];
            s += Math.max(1, badCharShift);
        }
    }
    
    return matches;
}

function buildBadCharTable(pattern) {
    const m = pattern.length;
    const NO_OF_CHARS = 256;
    const badChar = new Array(NO_OF_CHARS).fill(-1);
    
    // Fill the actual value of last occurrence
    for (let i = 0; i < m; i++) {
        badChar[pattern.charCodeAt(i)] = i;
    }
    
    return badChar;
}

console.log(boyerMooreSearch("ABAAABCD", "ABC"));
// Output: [4]

console.log(boyerMooreSearch("AABAACAADAABAABA", "AABA"));
// Output: [0, 9, 12]

// Best case: O(n/m) when pattern never matches
// Example: Pattern "ABCD" in "ZZZZZZZZ"
//          Can skip m characters at each mismatch

Note: Boyer-Moore is often the fastest practical algorithm for searching text, especially with large alphabets (like English). The bad character heuristic allows skipping multiple characters when a mismatch occurs.

6. Aho-Corasick Multiple Pattern Search

Component	Description	Purpose
Trie	Build trie of all patterns	Efficient prefix matching
Failure Links	Link to longest proper suffix that's also in trie	Navigate on mismatch like KMP
Output Links	Link to other patterns that end at current position	Report all matching patterns
Preprocessing	`O(∑m)` where ∑m is total pattern length	Build trie + compute failure links
Matching	`O(n + k)` where k is number of matches	Linear in text length + output
Applications	Virus scanning, spam filtering, DNA analysis	Search for thousands of patterns simultaneously

Example: Aho-Corasick Algorithm

class AhoCorasick {
    constructor(patterns) {
        this.trie = {children: {}, output: [], fail: null};
        this.buildTrie(patterns);
        this.buildFailureLinks();
    }
    
    buildTrie(patterns) {
        // Insert all patterns into trie
        for (let i = 0; i < patterns.length; i++) {
            let node = this.trie;
            
            for (const char of patterns[i]) {
                if (!node.children[char]) {
                    node.children[char] = {
                        children: {},
                        output: [],
                        fail: null
                    };
                }
                node = node.children[char];
            }
            
            // Mark end of pattern
            node.output.push(i);
        }
    }
    
    buildFailureLinks() {
        const queue = [];
        
        // Root failure link points to itself
        this.trie.fail = this.trie;
        
        // First level failure links point to root
        for (const char in this.trie.children) {
            const child = this.trie.children[char];
            child.fail = this.trie;
            queue.push(child);
        }
        
        // BFS to build failure links
        while (queue.length > 0) {
            const current = queue.shift();
            
            for (const char in current.children) {
                const child = current.children[char];
                queue.push(child);
                
                // Find failure link
                let failNode = current.fail;
                while (failNode !== this.trie && !failNode.children[char]) {
                    failNode = failNode.fail;
                }
                
                child.fail = failNode.children[char] || this.trie;
                
                // Inherit outputs from failure link
                child.output = child.output.concat(child.fail.output);
            }
        }
    }
    
    search(text) {
        const results = [];
        let node = this.trie;
        
        for (let i = 0; i < text.length; i++) {
            const char = text[i];
            
            // Follow failure links until we find a match
            while (node !== this.trie && !node.children[char]) {
                node = node.fail;
            }
            
            node = node.children[char] || this.trie;
            
            // Report all patterns ending at this position
            for (const patternIndex of node.output) {
                results.push({
                    pattern: patternIndex,
                    position: i
                });
            }
        }
        
        return results;
    }
}

// Example usage
const patterns = ["he", "she", "his", "hers"];
const ac = new AhoCorasick(patterns);
const text = "ushers";

const matches = ac.search(text);
console.log("Patterns:", patterns);
console.log("Text:", text);
console.log("Matches:", matches);
// Output: [
//   {pattern: 1, position: 2}, // "she" at position 0-2
//   {pattern: 0, position: 3}, // "he" at position 2-3
//   {pattern: 3, position: 5}  // "hers" at position 2-5
// ]

// Time: O(n + k) where k is number of matches
// Can find ALL patterns in single pass!

7. Manacher Longest Palindromic Substring

Aspect	Description	Innovation
Problem	Find longest palindromic substring in `O(n)`	Naive approach is O(n²) or O(n²) with DP
Preprocessing	Insert '#' between characters	Handles even/odd length palindromes uniformly
P Array	P[i] = radius of palindrome centered at i	Reuse previously computed information
Mirror Property	Use symmetry of palindromes to avoid recomputation	Core insight for linear time
Time Complexity	`O(n)`	Each position expanded at most once
Applications	DNA analysis, pattern recognition, compression	Finding all palindromes in linear time

Example: Manacher's Algorithm

function manacher(s) {
    // Preprocess: insert '#' between characters
    // "abc" becomes "#a#b#c#"
    const t = '#' + s.split('').join('#') + '#';
    const n = t.length;
    const p = new Array(n).fill(0); // Palindrome radius array
    
    let center = 0; // Center of rightmost palindrome
    let right = 0;  // Right boundary of rightmost palindrome
    
    for (let i = 0; i < n; i++) {
        // Mirror of i with respect to center
        const mirror = 2 * center - i;
        
        // If i is within right boundary, use mirror
        if (i < right) {
            p[i] = Math.min(right - i, p[mirror]);
        }
        
        // Expand around center i
        while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 &&
               t[i + p[i] + 1] === t[i - p[i] - 1]) {
            p[i]++;
        }
        
        // Update center and right if palindrome extends beyond right
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    
    // Find maximum palindrome
    let maxLen = 0;
    let centerIndex = 0;
    
    for (let i = 0; i < n; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            centerIndex = i;
        }
    }
    
    // Extract palindrome from original string
    const start = Math.floor((centerIndex - maxLen) / 2);
    return s.substring(start, start + maxLen);
}

console.log(manacher("babad"));      // Output: "bab" or "aba"
console.log(manacher("cbbd"));       // Output: "bb"
console.log(manacher("racecar"));    // Output: "racecar"
console.log(manacher("bananas"));    // Output: "anana"

// Time: O(n), Space: O(n)

Example: Find All Palindromes with Manacher

function findAllPalindromes(s) {
    const t = '#' + s.split('').join('#') + '#';
    const n = t.length;
    const p = new Array(n).fill(0);
    const palindromes = [];
    
    let center = 0, right = 0;
    
    // Build P array using Manacher's algorithm
    for (let i = 0; i < n; i++) {
        const mirror = 2 * center - i;
        if (i < right) p[i] = Math.min(right - i, p[mirror]);
        
        while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 &&
               t[i + p[i] + 1] === t[i - p[i] - 1]) {
            p[i]++;
        }
        
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    
    // Extract all palindromes
    for (let i = 0; i < n; i++) {
        if (p[i] > 0) {
            const start = Math.floor((i - p[i]) / 2);
            const length = p[i];
            if (length > 0) {
                const palindrome = s.substring(start, start + length);
                palindromes.push({
                    text: palindrome,
                    start: start,
                    length: length
                });
            }
        }
    }
    
    return palindromes;
}

const allPalindromes = findAllPalindromes("abacabad");
console.log(allPalindromes);
// Output includes: "aba", "aca", "aba", "abacaba", etc.
// All palindromes found in O(n) time!

8. Suffix Array Construction

Concept	Description	Use Case
Suffix Array	Sorted array of all suffixes of string	Compressed alternative to suffix tree
Construction	Naive: `O(n² log n)`, Optimized: `O(n log n)`	Various algorithms: prefix doubling, DC3
Pattern Search	Binary search on suffix array: `O(m log n)`	Multiple searches after one-time construction
LCP Array	Longest Common Prefix between consecutive suffixes	Finding repeated substrings, compression
Space	`O(n)`	More memory-efficient than suffix tree
Applications	Text compression, genome assembly, data compression	Burrows-Wheeler transform, FM-index

Example: Suffix Array (Simple Construction)

function buildSuffixArray(text) {
    const n = text.length;
    const suffixes = [];
    
    // Create array of (suffix, original index) pairs
    for (let i = 0; i < n; i++) {
        suffixes.push({
            index: i,
            suffix: text.substring(i)
        });
    }
    
    // Sort suffixes lexicographically
    suffixes.sort((a, b) => a.suffix.localeCompare(b.suffix));
    
    // Extract indices
    return suffixes.map(s => s.index);
}

const text = "banana";
const sa = buildSuffixArray(text);

console.log("Text:", text);
console.log("Suffix Array:", sa);
// Output: [5, 3, 1, 0, 4, 2]
// Meaning:
// sa[0] = 5: "a" (banana[5:])
// sa[1] = 3: "ana" (banana[3:])
// sa[2] = 1: "anana" (banana[1:])
// sa[3] = 0: "banana" (banana[0:])
// sa[4] = 4: "na" (banana[4:])
// sa[5] = 2: "nana" (banana[2:])

console.log("\nSorted Suffixes:");
sa.forEach((index, i) => {
    console.log(`${i}: ${text.substring(index)}`);
});

// Time: O(n² log n) for naive approach
// Space: O(n)

Example: Pattern Search using Suffix Array

function searchPattern(text, pattern, suffixArray) {
    const n = text.length;
    const m = pattern.length;
    
    // Binary search for leftmost occurrence
    let left = 0, right = n - 1;
    let leftBound = -1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const suffix = text.substring(suffixArray[mid]);
        
        if (suffix.substring(0, m) >= pattern) {
            right = mid - 1;
            if (suffix.substring(0, m) === pattern) {
                leftBound = mid;
            }
        } else {
            left = mid + 1;
        }
    }
    
    if (leftBound === -1) return []; // Pattern not found
    
    // Binary search for rightmost occurrence
    left = 0;
    right = n - 1;
    let rightBound = -1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const suffix = text.substring(suffixArray[mid]);
        
        if (suffix.substring(0, m) <= pattern) {
            left = mid + 1;
            if (suffix.substring(0, m) === pattern) {
                rightBound = mid;
            }
        } else {
            right = mid - 1;
        }
    }
    
    // All occurrences are in range [leftBound, rightBound]
    const positions = [];
    for (let i = leftBound; i <= rightBound; i++) {
        positions.push(suffixArray[i]);
    }
    
    return positions.sort((a, b) => a - b);
}

const text2 = "abracadabra";
const sa2 = buildSuffixArray(text2);

console.log(searchPattern(text2, "abra", sa2));
// Output: [0, 7] - "abra" found at positions 0 and 7

console.log(searchPattern(text2, "cad", sa2));
// Output: [4] - "cad" found at position 4

// Search Time: O(m log n) for pattern of length m

9. Edit Distance Levenshtein DP

Operation	Description	Cost
Insert	Add a character	1 (typically)
Delete	Remove a character	1 (typically)
Replace	Change one character to another	1 or 2 (Levenshtein vs Damerau)
Algorithm	Dynamic programming with 2D table	dp[i][j] = min operations for s1[0..i] to s2[0..j]
Time Complexity	`O(m × n)`	Fill m×n table
Space Complexity	`O(m × n)` or `O(min(m,n))` optimized	Can use rolling array for space optimization
Applications	Spell checking, DNA sequencing, diff tools, autocorrect	Measuring string similarity

Example: Edit Distance (Levenshtein)

function editDistance(str1, str2) {
    const m = str1.length;
    const n = str2.length;
    
    // Create DP table
    const dp = Array(m + 1).fill(null)
                           .map(() => Array(n + 1).fill(0));
    
    // Base cases: empty string conversions
    for (let i = 0; i <= m; i++) dp[i][0] = i; // Delete all
    for (let j = 0; j <= n; j++) dp[0][j] = j; // Insert all
    
    // Fill DP table
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (str1[i - 1] === str2[j - 1]) {
                // Characters match, no operation needed
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // Take minimum of insert, delete, replace
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j],     // Delete from str1
                    dp[i][j - 1],     // Insert into str1
                    dp[i - 1][j - 1]  // Replace in str1
                );
            }
        }
    }
    
    return dp[m][n];
}

console.log(editDistance("kitten", "sitting"));
// Output: 3 (kitten → sitten → sittin → sitting)

console.log(editDistance("sunday", "saturday"));
// Output: 3 (sunday → sturday → saturay → saturday)

console.log(editDistance("horse", "ros"));
// Output: 3 (horse → rorse → rose → ros)

// Time: O(m × n), Space: O(m × n)

Example: Edit Distance with Path Reconstruction

function editDistanceWithPath(str1, str2) {
    const m = str1.length;
    const n = str2.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
    
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (str1[i - 1] === str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j],
                    dp[i][j - 1],
                    dp[i - 1][j - 1]
                );
            }
        }
    }
    
    // Reconstruct path
    const operations = [];
    let i = m, j = n;
    
    while (i > 0 || j > 0) {
        if (i === 0) {
            operations.push(`Insert '${str2[j - 1]}'`);
            j--;
        } else if (j === 0) {
            operations.push(`Delete '${str1[i - 1]}'`);
            i--;
        } else if (str1[i - 1] === str2[j - 1]) {
            operations.push(`Keep '${str1[i - 1]}'`);
            i--;
            j--;
        } else {
            const deleteCost = dp[i - 1][j];
            const insertCost = dp[i][j - 1];
            const replaceCost = dp[i - 1][j - 1];
            
            if (replaceCost <= deleteCost && replaceCost <= insertCost) {
                operations.push(`Replace '${str1[i - 1]}' with '${str2[j - 1]}'`);
                i--;
                j--;
            } else if (deleteCost <= insertCost) {
                operations.push(`Delete '${str1[i - 1]}'`);
                i--;
            } else {
                operations.push(`Insert '${str2[j - 1]}'`);
                j--;
            }
        }
    }
    
    return {
        distance: dp[m][n],
        operations: operations.reverse()
    };
}

const result = editDistanceWithPath("kitten", "sitting");
console.log("Distance:", result.distance);
console.log("Operations:", result.operations);
// Shows exact sequence of operations to transform string

10. Trie-based String Operations

Operation	Time Complexity	Description
Insert	`O(m)`	Add word of length m to trie
Search	`O(m)`	Check if word exists
Prefix Search	`O(m)`	Find all words with given prefix
Delete	`O(m)`	Remove word from trie
Autocomplete	`O(m + k)`	Find k suggestions for prefix m
Space	`O(ALPHABET_SIZE × N × M)`	N words, M avg length, can be optimized

Example: Trie with Autocomplete

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
        this.frequency = 0; // For ranking suggestions
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    
    insert(word, frequency = 1) {
        let node = this.root;
        
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        
        node.isEndOfWord = true;
        node.frequency = frequency;
    }
    
    search(word) {
        let node = this.root;
        
        for (const char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        
        return node.isEndOfWord;
    }
    
    startsWith(prefix) {
        let node = this.root;
        
        for (const char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        
        return true;
    }
    
    autocomplete(prefix, limit = 5) {
        let node = this.root;
        
        // Navigate to prefix
        for (const char of prefix) {
            if (!node.children[char]) {
                return [];
            }
            node = node.children[char];
        }
        
        // DFS to find all words with this prefix
        const suggestions = [];
        this.dfs(node, prefix, suggestions);
        
        // Sort by frequency and return top results
        return suggestions
            .sort((a, b) => b.frequency - a.frequency)
            .slice(0, limit)
            .map(s => s.word);
    }
    
    dfs(node, currentWord, suggestions) {
        if (node.isEndOfWord) {
            suggestions.push({
                word: currentWord,
                frequency: node.frequency
            });
        }
        
        for (const char in node.children) {
            this.dfs(node.children[char], currentWord + char, suggestions);
        }
    }
    
    delete(word) {
        this.deleteHelper(this.root, word, 0);
    }
    
    deleteHelper(node, word, index) {
        if (index === word.length) {
            if (!node.isEndOfWord) return false;
            node.isEndOfWord = false;
            return Object.keys(node.children).length === 0;
        }
        
        const char = word[index];
        if (!node.children[char]) return false;
        
        const shouldDeleteChild = this.deleteHelper(
            node.children[char],
            word,
            index + 1
        );
        
        if (shouldDeleteChild) {
            delete node.children[char];
            return Object.keys(node.children).length === 0 && !node.isEndOfWord;
        }
        
        return false;
    }
}

// Example usage
const trie = new Trie();

// Insert words with frequencies
const words = [
    {word: "apple", freq: 100},
    {word: "app", freq: 80},
    {word: "application", freq: 60},
    {word: "apply", freq: 70},
    {word: "appreciate", freq: 50},
    {word: "apricot", freq: 30}
];

words.forEach(({word, freq}) => trie.insert(word, freq));

console.log(trie.search("apple"));        // true
console.log(trie.search("appl"));         // false
console.log(trie.startsWith("app"));      // true

console.log(trie.autocomplete("app", 3));
// Output: ["apple", "app", "apply"] - Top 3 by frequency

console.log(trie.autocomplete("appr", 5));
// Output: ["appreciate"]

trie.delete("app");
console.log(trie.search("app"));          // false
console.log(trie.search("apple"));        // true (still exists)

String Algorithms Summary

Naive: O(n×m), simple but slow, good for teaching/debugging
KMP: O(n+m), no backtracking, LPS array, single pattern optimal
Rabin-Karp: O(n+m) avg, rolling hash, great for multiple patterns
Z Algorithm: O(n+m), Z array, simpler than KMP for some problems
Boyer-Moore: O(n/m) best, fastest in practice, used in grep/editors
Aho-Corasick: O(n+k), multiple patterns simultaneously, virus scanning
Manacher: O(n), longest palindrome, mirror property optimization
Suffix Array: O(n log n) build, O(m log n) search, genome analysis
Edit Distance: O(m×n), DP solution, spell check, DNA alignment
Trie: O(m) operations, prefix matching, autocomplete, dictionaries

Related Cheatsheets

Datastructures-algorithms