// ─────────────────────────────────────────────────────────────────────────────
// STRINGS
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : character-level scanning, frequency tables, and parsing.
// TELL   : "palindrome", "anagram", "lowercase letters only" (-> array[26]),
//          "substring", "prefix", "parse", "compress".
// SAY    : two pointers, frequency array / counting, expand around center,
//          canonical key (sorted string), KMP failure (LPS) table, char code arithmetic.
// BIG-O  : O(n) scans; O(n^2) for expand-around-center; O(n k log k) for sorted keys.
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── 0. Char-code arithmetic  —  'a'.charCodeAt(0) === 97; index = code - 97; back: String.fromCharCode(97 + i)
const A = 'a'.charCodeAt(0);
const idx = (ch) => ch.charCodeAt(0) - A;
const chr = (i) => String.fromCharCode(A + i);
assert.equal(idx('c'), 2);
assert.equal(chr(25), 'z');
assert.equal(String.fromCharCode(...[104, 105]), 'hi');

// ── 1. Palindrome check (two pointers)  —  compare from both ends inward  —  O(n) / O(1)
function isPalindrome(s) {
  let i = 0, j = s.length - 1;
  while (i < j) if (s[i++] !== s[j--]) return false;
  return true;
}
assert.equal(isPalindrome('racecar'), true);
assert.equal(isPalindrome('ab'), false);
assert.equal(isPalindrome(''), true);

// ── 2. Valid anagram (frequency array of 26)  —  +1 for s, -1 for t, all zero  —  O(n) / O(1)
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const freq = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) { freq[idx(s[i])]++; freq[idx(t[i])]--; }
  return freq.every((c) => c === 0);
}
assert.equal(isAnagram('anagram', 'nagaram'), true);
assert.equal(isAnagram('rat', 'car'), false);
assert.equal(isAnagram('', ''), true);

// ── 3. Reverse words  —  split on whitespace, filter empties, reverse, join  —  O(n) / O(n)
const reverseWords = (s) => s.split(/\s+/).filter(Boolean).reverse().join(' ');
assert.equal(reverseWords('the sky is blue'), 'blue is sky the');
assert.equal(reverseWords('  hello   world  '), 'world hello');
assert.equal(reverseWords(''), '');

// ── 4. Longest palindromic substring (expand around center)  —  2n-1 centers (odd + even)  —  O(n^2) / O(1)
function longestPalindrome(s) {
  let best = '';
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    if (r - l - 1 > best.length) best = s.slice(l + 1, r);
  };
  for (let i = 0; i < s.length; i++) { expand(i, i); expand(i, i + 1); }
  return best;
}
assert.equal(longestPalindrome('babad'), 'bab');
assert.equal(longestPalindrome('cbbd'), 'bb');
assert.equal(longestPalindrome(''), '');

// ── 5. Longest common prefix  —  shrink prefix until every word startsWith it  —  O(S) total chars / O(1)
function longestCommonPrefix(strs) {
  if (strs.length === 0) return '';
  let p = strs[0];
  for (const w of strs) while (!w.startsWith(p)) p = p.slice(0, -1);
  return p;
}
assert.equal(longestCommonPrefix(['flower', 'flow', 'flight']), 'fl');
assert.equal(longestCommonPrefix(['dog', 'racecar']), '');
assert.equal(longestCommonPrefix([]), '');

// ── 6. String compression (run-length)  —  count runs; emit char + count if > 1  —  O(n) / O(n)
function compress(s) {
  let out = '';
  for (let i = 0; i < s.length;) {
    let j = i;
    while (j < s.length && s[j] === s[i]) j++;
    out += s[i] + (j - i > 1 ? j - i : '');
    i = j;
  }
  return out;
}
assert.equal(compress('aabcccc'), 'a2bc4');
assert.equal(compress('abc'), 'abc');
assert.equal(compress(''), '');

// ── 7. First unique character  —  count pass, then first index with count 1  —  O(n) / O(1)
function firstUniqChar(s) {
  const freq = new Map();
  for (const c of s) freq.set(c, (freq.get(c) ?? 0) + 1);
  for (let i = 0; i < s.length; i++) if (freq.get(s[i]) === 1) return i;
  return -1;
}
assert.equal(firstUniqChar('leetcode'), 0);
assert.equal(firstUniqChar('loveleetcode'), 2);
assert.equal(firstUniqChar('aabb'), -1);

// ── 8. Isomorphic strings  —  bijection: two maps s->t and t->s must agree  —  O(n) / O(1)
function isIsomorphic(s, t) {
  if (s.length !== t.length) return false;
  const st = new Map(), ts = new Map();
  for (let i = 0; i < s.length; i++) {
    const a = s[i], b = t[i];
    if ((st.has(a) && st.get(a) !== b) || (ts.has(b) && ts.get(b) !== a)) return false;
    st.set(a, b); ts.set(b, a);
  }
  return true;
}
assert.equal(isIsomorphic('egg', 'add'), true);
assert.equal(isIsomorphic('foo', 'bar'), false);
assert.equal(isIsomorphic('badc', 'baba'), false);

// ── 9. Group anagrams (sorted key)  —  key = chars sorted; Map key -> list  —  O(n k log k) / O(nk)
function groupAnagrams(strs) {
  const groups = new Map();
  for (const w of strs) {
    const key = [...w].sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(w);
  }
  return [...groups.values()];
}
assert.deepEqual(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']), [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]);
assert.deepEqual(groupAnagrams(['']), [['']]);

// ── 10. atoi-style parse with overflow clamp  —  skip ws, sign, digits, clamp to int32  —  O(n) / O(1)
function myAtoi(s) {
  const INT_MAX = 2 ** 31 - 1, INT_MIN = -(2 ** 31);
  let i = 0, sign = 1, num = 0;
  while (s[i] === ' ') i++;
  if (s[i] === '+' || s[i] === '-') sign = s[i++] === '-' ? -1 : 1;
  while (i < s.length && s[i] >= '0' && s[i] <= '9') {
    num = num * 10 + (s.charCodeAt(i++) - 48);
    if (sign * num > INT_MAX) return INT_MAX;
    if (sign * num < INT_MIN) return INT_MIN;
  }
  return sign * num;
}
assert.equal(myAtoi('   -42abc'), -42);
assert.equal(myAtoi('91283472332'), 2147483647);
assert.equal(myAtoi('words 987'), 0);

// ── 11. Roman to integer  —  if value < next value, subtract; else add  —  O(n) / O(1)
function romanToInt(s) {
  const v = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };
  let total = 0;
  for (let i = 0; i < s.length; i++) total += v[s[i]] < (v[s[i + 1]] ?? 0) ? -v[s[i]] : v[s[i]];
  return total;
}
assert.equal(romanToInt('MCMXCIV'), 1994);
assert.equal(romanToInt('LVIII'), 58);
assert.equal(romanToInt('I'), 1);

// ── 12. KMP failure table (LPS: longest proper prefix that is also a suffix)  —  lps[i] for pattern[0..i]  —  O(m) / O(m)
function buildLPS(p) {
  const lps = new Array(p.length).fill(0);
  for (let i = 1, len = 0; i < p.length;) {
    if (p[i] === p[len]) lps[i++] = ++len;
    else if (len > 0) len = lps[len - 1]; // fall back, do not advance i
    else lps[i++] = 0;
  }
  return lps;
}
// KMP search  —  on mismatch jump j = lps[j-1] instead of restarting  —  O(n + m)
function kmpSearch(text, p) {
  if (p.length === 0) return 0;
  const lps = buildLPS(p);
  for (let i = 0, j = 0; i < text.length;) {
    if (text[i] === p[j]) { i++; j++; if (j === p.length) return i - j; }
    else if (j > 0) j = lps[j - 1];
    else i++;
  }
  return -1;
}
assert.deepEqual(buildLPS('aabaaab'), [0, 1, 0, 1, 2, 2, 3]);
assert.deepEqual(buildLPS('abcd'), [0, 0, 0, 0]);
assert.equal(kmpSearch('abxabcabcaby', 'abcaby'), 6);
assert.equal(kmpSearch('aaaa', 'b'), -1);

console.log('ok: algorithms/strings.js');