// In-place two-pointer reversal (array input, LeetCode 344)
function reverseString(s) {
  let left = 0, right = s.length - 1;
  while (left < right) {
    [s[left], s[right]] = [s[right], s[left]];
    left++;
    right--;
  }
}

// If you receive a plain string (immutable), convert first
function reverseStr(s) {
  return s.split('').reverse().join('');
  // or manually:
  // const arr = s.split('');
  // let l = 0, r = arr.length - 1;
  // while (l < r) { [arr[l], arr[r]] = [arr[r], arr[l]]; l++; r--; }
  // return arr.join('');
}

console.log(reverseStr('hello'));   // 'olleh'
console.log(reverseStr('abcde'));   // 'edcba'

function isPalindrome(s) {
  // helper: is the character alphanumeric?
  const isAlphaNum = ch => /[a-z0-9]/.test(ch.toLowerCase());

  let left = 0, right = s.length - 1;
  while (left < right) {
    // skip non-alphanumeric from both ends
    while (left < right && !isAlphaNum(s[left]))  left++;
    while (left < right && !isAlphaNum(s[right])) right--;

    if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
    left++;
    right--;
  }
  return true;
}

console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car"));                     // false
console.log(isPalindrome(" "));                              // true

function compress(s) {
  if (!s.length) return s;

  const result = [];
  let i = 0;

  while (i < s.length) {
    const ch = s[i];
    let count = 0;
    // count consecutive occurrences
    while (i < s.length && s[i] === ch) {
      i++;
      count++;
    }
    result.push(ch);
    if (count > 1) result.push(count);
  }

  const compressed = result.join('');
  return compressed.length < s.length ? compressed : s;
}

console.log(compress('aaabbc'));   // 'a3b2c1' — wait, c1 is same length
// Actually: 'a3b2c1'.length === 6 === 'aaabbc'.length, return original
console.log(compress('aaaaabbb')); // 'a5b3' (shorter, return it)
console.log(compress('abc'));      // 'abc'  (a1b1c1 longer, return original)

// LeetCode 443 variant: compress in-place with two pointers
function compressInPlace(chars) {
  let write = 0, i = 0;
  while (i < chars.length) {
    const ch = chars[i];
    let count = 0;
    while (i < chars.length && chars[i] === ch) { i++; count++; }
    chars[write++] = ch;
    if (count > 1) {
      for (const digit of String(count)) {
        chars[write++] = digit;
      }
    }
  }
  return write; // new length
}

function longestCommonPrefix(strs) {
  if (!strs.length) return '';

  for (let col = 0; col < strs[0].length; col++) {
    const ch = strs[0][col];
    for (let row = 1; row < strs.length; row++) {
      // mismatch: current column doesn't match, OR string is too short
      if (col >= strs[row].length || strs[row][col] !== ch) {
        return strs[0].slice(0, col);
      }
    }
  }
  return strs[0]; // all characters matched
}

console.log(longestCommonPrefix(['flower','flow','flight'])); // 'fl'
console.log(longestCommonPrefix(['dog','racecar','car']));    // ''
console.log(longestCommonPrefix(['abc']));                    // 'abc'

function isIsomorphic(s, t) {
  if (s.length !== t.length) return false;

  const sToT = new Map(); // s char → t char
  const tToS = new Map(); // t char → s char

  for (let i = 0; i < s.length; i++) {
    const sc = s[i], tc = t[i];

    if (sToT.has(sc) && sToT.get(sc) !== tc) return false;
    if (tToS.has(tc) && tToS.get(tc) !== sc) return false;

    sToT.set(sc, tc);
    tToS.set(tc, sc);
  }
  return true;
}

console.log(isIsomorphic('egg', 'add'));  // true  (e→a, g→d)
console.log(isIsomorphic('foo', 'bar'));  // false (o maps to both a and r)
console.log(isIsomorphic('paper', 'title')); // true

function groupAnagrams(strs) {
  const map = new Map();

  for (const s of strs) {
    const key = s.split('').sort().join(''); // canonical form
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }

  return [...map.values()];
}

console.log(groupAnagrams(['eat','tea','tan','ate','nat','bat']));
// [['eat','tea','ate'], ['tan','nat'], ['bat']]

// O(n) alternative: encode frequency as key instead of sorting
function groupAnagramsLinear(strs) {
  const map = new Map();
  const a = 'a'.charCodeAt(0);

  for (const s of strs) {
    const freq = new Array(26).fill(0);
    for (const ch of s) freq[ch.charCodeAt(0) - a]++;
    const key = freq.join('#'); // e.g. "1#0#0...#1#..."
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}

function isRotation(s1, s2) {
  if (s1.length !== s2.length) return false;
  return (s1 + s1).includes(s2);
  // For production, replace .includes with KMP for O(n) guarantee
}

console.log(isRotation('abcde', 'cdeab')); // true
console.log(isRotation('abcde', 'abced')); // false
console.log(isRotation('abc',   'cab'));   // true

// Why it works:
// s1 = "abcde",  s1+s1 = "abcdeabcde"
// All rotations: abcde, bcdea, cdeab, deabc, eabcd — all substrings of s1+s1

// Naive O(n·m) — acceptable for most interviews
function strStr(haystack, needle) {
  if (needle.length === 0) return 0;
  const n = haystack.length, m = needle.length;

  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && haystack[i + j] === needle[j]) j++;
    if (j === m) return i; // full match found
  }
  return -1;
}

console.log(strStr('hello', 'll'));    // 2
console.log(strStr('aaaaa', 'bba'));   // -1
console.log(strStr('', ''));           // 0

// One-liner using built-in (same semantics)
const strStrBuiltin = (h, n) => h.indexOf(n);