Strings

// ===== Search (substring) =====
// Built-in (most languages):
'hello world'.indexOf('world')        // 6
'hello world'.includes('world')        // true

// Naive O(n*m), KMP O(n + m), Boyer-Moore sublinear on average.
// Use built-in unless writing the algorithm IS the assignment.

// ===== Anagram check =====
function isAnagram(a, b) {
  if (a.length !== b.length) return false;
  const c = {};
  for (const ch of a) c[ch] = (c[ch] ?? 0) + 1;
  for (const ch of b) {
    if (!c[ch]) return false;
    c[ch]--;
  }
  return true;
}

// ===== Palindrome (in place) =====
function isPal(s) {
  let i = 0, j = s.length - 1;
  while (i < j) { if (s[i] !== s[j]) return false; i++; j--; }
  return true;
}

// ===== Longest substring without repeating chars =====
function longestUnique(s) {
  const last = new Map();
  let start = 0, best = 0;
  for (let i = 0; i < s.length; i++) {
    if (last.has(s[i]) && last.get(s[i]) >= start) start = last.get(s[i]) + 1;
    last.set(s[i], i);
    best = Math.max(best, i - start + 1);
  }
  return best;
}

// ===== Edit distance (Levenshtein) =====
function editDistance(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => Array(b.length + 1).fill(0));
  for (let i = 0; i <= a.length; i++) dp[i][0] = i;
  for (let j = 0; j <= b.length; j++) dp[0][j] = j;
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      dp[i][j] = a[i-1] === b[j-1]
        ? dp[i-1][j-1]
        : 1 + Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[a.length][b.length];
}

// ===== Trie (prefix tree) =====
class Trie {
  constructor() { this.root = {}; }
  insert(word) {
    let node = this.root;
    for (const ch of word) node = (node[ch] ??= {});
    node['*'] = true;
  }
  startsWith(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node[ch]) return false;
      node = node[ch];
    }
    return true;
  }
}

// Use for: autocomplete, prefix lookup, dictionary search.

// ===== Rolling hash (Rabin-Karp) =====
// Fast substring search across many patterns; great for plagiarism detection.

// ===== KMP failure function =====
// Pattern-internal table speeds up search by avoiding rechecks.
// Useful when you do many searches of the same pattern.

// ===== Common interview patterns =====
// - Two pointers: palindromes, longest substring problems
// - Sliding window: substring with constraints
// - Hash maps: anagrams, character counts
// - Tries: autocomplete, dictionary problems
// - Dynamic programming: edit distance, longest common subseq, regex matching

// ===== Unicode caveats =====
// JS '😀'.length === 2 because of UTF-16 surrogate pairs.
// Use [...str] or Array.from(str) to iterate by code points.

// ===== Patterns to internalise =====
// - indexOf / includes / .startsWith / .endsWith before reaching for KMP
// - Tries for prefix-heavy workloads
// - Hash maps for character counts (anagrams, char frequencies)
// - Sliding window + two pointers cover most substring problems

// ===== Pitfalls =====
// - .length on emoji / accented strings (UTF-16 surrogate pairs)
// - Regex on huge strings without anchors -> ReDoS risk
// - Building strings in a loop with + (O(n^2)); use arrays + .join()
// - Locale-dependent comparisons; use Intl.Collator for proper sorting

// Strings are arrays of code units.
// Reverse with two pointers:
function reverse(s) {
    const a = s.split('');
    for (let l = 0, r = a.length - 1; l < r; l++, r--) [a[l], a[r]] = [a[r], a[l]];
    return a.join('');
}