String

function isPalindrome(s) {
  let l = 0, r = s.length - 1;
  while (l < r) if (s[l++] !== s[r--]) return false;
  return true;
}

const isPalindrome = (s) => s === [...s].reverse().join('');

function longestPalindrome(s) {
  let best = '';
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    return s.slice(l + 1, r);
  };
  for (let i = 0; i < s.length; i++) {
    for (const p of [expand(i, i), expand(i, i + 1)])
      if (p.length > best.length) best = p;
  }
  return best;
}

function longestPalindrome(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(false));
  let start = 0, maxLen = 1;
  for (let i = 0; i < n; i++) dp[i][i] = true;
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      if (s[i] === s[j] && (len === 2 || dp[i + 1][j - 1])) {
        dp[i][j] = true;
        if (len > maxLen) { start = i; maxLen = len; }
      }
    }
  }
  return s.slice(start, start + maxLen);
}

function longestCommonPrefix(strs) {
  if (!strs.length) return '';
  for (let i = 0; i < strs[0].length; i++) {
    const c = strs[0][i];
    for (const s of strs) if (i === s.length || s[i] !== c) return strs[0].slice(0, i);
  }
  return strs[0];
}

function longestCommonPrefix(strs) {
  if (!strs.length) return '';
  strs.sort();
  const a = strs[0], b = strs[strs.length - 1];
  let i = 0;
  while (i < a.length && a[i] === b[i]) i++;
  return a.slice(0, i);
}

function minWindow(s, t) {
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  let missing = t.length, start = 0, resStart = 0, resLen = Infinity;
  for (let end = 0; end < s.length; end++) {
    const c = s[end];
    if (need.get(c) > 0) missing--;
    need.set(c, (need.get(c) || 0) - 1);
    while (missing === 0) {
      if (end - start + 1 < resLen) { resLen = end - start + 1; resStart = start; }
      const lc = s[start++];
      need.set(lc, need.get(lc) + 1);
      if (need.get(lc) > 0) missing++;
    }
  }
  return resLen === Infinity ? '' : s.slice(resStart, resStart + resLen);
}

function isValid(s) {
  const pair = { ')': '(', ']': '[', '}': '{' };
  const st = [];
  for (const c of s) {
    if (c === '(' || c === '[' || c === '{') st.push(c);
    else if (st.pop() !== pair[c]) return false;
  }
  return st.length === 0;
}

function reverseString(s) {
  const a = [...s];
  let l = 0, r = a.length - 1;
  while (l < r) { [a[l], a[r]] = [a[r], a[l]]; l++; r--; }
  return a.join('');
}

function duplicates(s) {
  const freq = new Map();
  for (const c of s) freq.set(c, (freq.get(c) || 0) + 1);
  return [...freq].filter(([, n]) => n > 1).map(([c, n]) => ({ char: c, count: n }));
}

function isRotation(a, b) {
  return a.length === b.length && (a + a).includes(b);
}

function isValidShuffle(a, b, result) {
  if (a.length + b.length !== result.length) return false;
  let i = 0, j = 0;
  for (const c of result) {
    if (i < a.length && a[i] === c) i++;
    else if (j < b.length && b[j] === c) j++;
    else return false;
  }
  return i === a.length && j === b.length;
}

function countAndSay(n) {
  let s = '1';
  for (let k = 1; k < n; k++) {
    let next = '', i = 0;
    while (i < s.length) {
      let j = i;
      while (j < s.length && s[j] === s[i]) j++;
      next += (j - i) + s[i];
      i = j;
    }
    s = next;
  }
  return s;
}

function longestRepeatingSubseq(s) {
  const n = s.length;
  const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = s[i - 1] === s[j - 1] && i !== j
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1]);
  return dp[n][n];
}

function maxSplits(s) {
  let zeros = 0, ones = 0, cuts = 0;
  for (const c of s) {
    c === '0' ? zeros++ : ones++;
    if (zeros === ones) cuts++;
  }
  return zeros === ones ? cuts : -1; // -1 if the whole string can't be balanced
}

function wordWrap(words, width) {
  const n = words.length;
  const dp = Array(n + 1).fill(Infinity);
  dp[n] = 0;
  for (let i = n - 1; i >= 0; i--) {
    let lineLen = -1;
    for (let j = i; j < n; j++) {
      lineLen += words[j].length + 1;
      if (lineLen > width) break;
      const extra = j === n - 1 ? 0 : (width - lineLen) ** 2;
      dp[i] = Math.min(dp[i], extra + dp[j + 1]);
    }
  }
  return dp[0];
}

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

function nextGreater(numStr) {
  const a = [...numStr];
  let i = a.length - 2;
  while (i >= 0 && a[i] >= a[i + 1]) i--;
  if (i < 0) return 'no greater number';
  let j = a.length - 1;
  while (a[j] <= a[i]) j--;
  [a[i], a[j]] = [a[j], a[i]];
  return a.slice(0, i + 1).join('') + a.slice(i + 1).reverse().join('');
}

function wordBreak(s, wordDict) {
  const dict = new Set(wordDict);
  const dp = Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (dp[j] && dict.has(s.slice(j, i))) { dp[i] = true; break; }
    }
  }
  return dp[s.length];
}

function rabinKarp(text, pat) {
  const n = text.length, m = pat.length;
  if (m > n) return [];
  const B = 256, MOD = 1_000_000_007;
  let pHash = 0, tHash = 0, pow = 1;
  for (let i = 0; i < m - 1; i++) pow = (pow * B) % MOD;
  for (let i = 0; i < m; i++) {
    pHash = (pHash * B + pat.charCodeAt(i)) % MOD;
    tHash = (tHash * B + text.charCodeAt(i)) % MOD;
  }
  const res = [];
  for (let i = 0; i + m <= n; i++) {
    if (pHash === tHash && text.slice(i, i + m) === pat) res.push(i);
    if (i + m < n) {
      tHash = ((tHash - text.charCodeAt(i) * pow) % MOD + MOD) % MOD;
      tHash = (tHash * B + text.charCodeAt(i + m)) % MOD;
    }
  }
  return res;
}

function kmp(text, pat) {
  const m = pat.length;
  const lps = Array(m).fill(0);
  for (let i = 1, len = 0; i < m; ) {
    if (pat[i] === pat[len]) lps[i++] = ++len;
    else if (len) len = lps[len - 1];
    else lps[i++] = 0;
  }
  const res = [];
  for (let i = 0, j = 0; i < text.length; ) {
    if (text[i] === pat[j]) { i++; j++; if (j === m) { res.push(i - m); j = lps[j - 1]; } }
    else if (j) j = lps[j - 1];
    else i++;
  }
  return res;
}

function keypadSequence(sentence) {
  const keys = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
  const map = {};
  for (let d = 2; d <= 9; d++)
    [...keys[d]].forEach((ch, i) => (map[ch] = String(d).repeat(i + 1)));
  return [...sentence.toLowerCase()].map((c) => (c === ' ' ? '0' : map[c] || '')).join('');
}

function minReversals(s) {
  if (s.length % 2) return -1;
  let open = 0, close = 0;
  for (const c of s) {
    if (c === '{') open++;
    else if (open > 0) open--;   // matched a pair
    else close++;                // an unmatched '}'
  }
  return Math.ceil(open / 2) + Math.ceil(close / 2);
}

function minSwaps(s) {
  let balance = 0, swaps = 0, imbalance = 0;
  for (const c of s) {
    if (c === '[') {
      balance++;
      if (imbalance > 0) { swaps += imbalance; imbalance--; }
    } else {
      balance--;
      if (balance < 0) imbalance++;
    }
  }
  return swaps;
}

function countPalindromicSubseq(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(0));
  for (let i = 0; i < n; i++) dp[i][i] = 1;
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0);
      if (s[i] === s[j]) dp[i][j] += 1 + (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0);
    }
  }
  return dp[0][n - 1];
}

function findWord(grid, word) {
  const R = grid.length, C = grid[0].length;
  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
  const hits = [];
  const ok = (r, c, dr, dc) => {
    for (let k = 0; k < word.length; k++) {
      const nr = r + dr * k, nc = c + dc * k;
      if (nr < 0 || nc < 0 || nr >= R || nc >= C || grid[nr][nc] !== word[k]) return false;
    }
    return true;
  };
  for (let r = 0; r < R; r++)
    for (let c = 0; c < C; c++)
      if (grid[r][c] === word[0])
        for (const [dr, dc] of dirs)
          if (ok(r, c, dr, dc)) hits.push([r, c, dr, dc]);
  return hits;
}

function boyerMoore(text, pat) {
  const n = text.length, m = pat.length;
  const last = new Map();
  for (let i = 0; i < m; i++) last.set(pat[i], i);
  const res = [];
  let s = 0;
  while (s <= n - m) {
    let j = m - 1;
    while (j >= 0 && pat[j] === text[s + j]) j--;
    if (j < 0) { res.push(s); s += m; }
    else {
      const lo = last.has(text[s + j]) ? last.get(text[s + j]) : -1;
      s += Math.max(1, j - lo);
    }
  }
  return res;
}

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++) {
    if (i + 1 < s.length && v[s[i]] < v[s[i + 1]]) total -= v[s[i]];
    else total += v[s[i]];
  }
  return total;
}

function minFlips(s) {
  let diff = 0;
  for (let i = 0; i < s.length; i++) {
    const expected = i % 2 === 0 ? '0' : '1';
    if (s[i] !== expected) diff++;
  }
  return Math.min(diff, s.length - diff);
}

function firstRepeatedWord(s) {
  const seen = new Set();
  for (const w of s.toLowerCase().split(/\s+/)) {
    if (seen.has(w)) return w;
    seen.add(w);
  }
  return null;
}

function smallestDistinctWindow(s) {
  const target = new Set(s).size;
  const count = new Map();
  let have = 0, start = 0, best = s;
  for (let end = 0; end < s.length; end++) {
    const c = s[end];
    count.set(c, (count.get(c) || 0) + 1);
    if (count.get(c) === 1) have++;
    while (have === target) {
      if (end - start + 1 < best.length) best = s.slice(start, end + 1);
      const lc = s[start++];
      count.set(lc, count.get(lc) - 1);
      if (count.get(lc) === 0) have--;
    }
  }
  return best;
}

function reorganize(s) {
  const freq = new Map();
  for (const c of s) freq.set(c, (freq.get(c) || 0) + 1);
  let res = '', prev = '';
  for (let i = 0; i < s.length; i++) {
    let best = '';
    for (const [c, n] of freq) if (n > 0 && c !== prev && (best === '' || n > freq.get(best))) best = c;
    if (best === '') return '';
    res += best;
    freq.set(best, freq.get(best) - 1);
    prev = best;
  }
  return res;
}

function minCharsFront(s) {
  const combined = s + '#' + [...s].reverse().join('');
  const lps = Array(combined.length).fill(0);
  for (let i = 1, len = 0; i < combined.length; ) {
    if (combined[i] === combined[len]) lps[i++] = ++len;
    else if (len) len = lps[len - 1];
    else lps[i++] = 0;
  }
  return s.length - lps[lps.length - 1];
}

function groupAnagrams(words) {
  const groups = new Map();
  for (const w of words) {
    const key = [...w].sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(w);
  }
  return [...groups.values()];
}

function restoreIps(s) {
  const res = [];
  const valid = (seg) => seg.length >= 1 && seg.length <= 3 &&
    (seg === '0' || (seg[0] !== '0' && +seg <= 255));
  const bt = (start, parts) => {
    if (parts.length === 4) { if (start === s.length) res.push(parts.join('.')); return; }
    for (let len = 1; len <= 3 && start + len <= s.length; len++) {
      const seg = s.slice(start, start + len);
      if (valid(seg)) bt(start + len, [...parts, seg]);
    }
  };
  bt(0, []);
  return res;
}

function removeAdjacentDuplicates(s) {
  const st = [];
  let i = 0;
  while (i < s.length) {
    if (st.length && st[st.length - 1] === s[i]) {
      const dup = s[i];
      while (i < s.length && s[i] === dup) i++;
      st.pop();
    } else {
      st.push(s[i++]);
    }
  }
  return st.join('');
}

function isMatch(text, pattern) {
  const n = text.length, m = pattern.length;
  const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(false));
  dp[0][0] = true;
  for (let j = 1; j <= m; j++) if (pattern[j - 1] === '*') dp[0][j] = dp[0][j - 1];
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= m; j++) {
      if (pattern[j - 1] === '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
      else if (pattern[j - 1] === '?' || pattern[j - 1] === text[i - 1]) dp[i][j] = dp[i - 1][j - 1];
    }
  return dp[n][m];
}

function turnedAway(seq, k) {
  const seated = new Set();
  const walkedAway = new Set();
  let turned = 0;
  for (const id of seq) {
    if (seated.has(id)) seated.delete(id);           // leaving
    else if (walkedAway.has(id)) walkedAway.delete(id); // second visit after being turned away
    else if (seated.size < k) seated.add(id);        // gets a seat
    else { turned++; walkedAway.add(id); }           // no seat
  }
  return turned;
}

function isIsomorphic(a, b) {
  if (a.length !== b.length) return false;
  const ab = new Map(), ba = new Map();
  for (let i = 0; i < a.length; i++) {
    if (ab.has(a[i]) && ab.get(a[i]) !== b[i]) return false;
    if (ba.has(b[i]) && ba.get(b[i]) !== a[i]) return false;
    ab.set(a[i], b[i]);
    ba.set(b[i], a[i]);
  }
  return true;
}

function allSentences(lists) {
  const res = [];
  const bt = (row, acc) => {
    if (row === lists.length) { res.push(acc.join(' ')); return; }
    for (const w of lists[row]) bt(row + 1, [...acc, w]);
  };
  bt(0, []);
  return res;
}

const isAnagram = (s, t) =>
  s.length === t.length && [...s].sort().join('') === [...t].sort().join('');

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const cnt = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    cnt[s.charCodeAt(i) - 97]++;
    cnt[t.charCodeAt(i) - 97]--;
  }
  return cnt.every((c) => c === 0);
}

function firstUniqChar(s) {
  const cnt = new Map();
  for (const c of s) cnt.set(c, (cnt.get(c) ?? 0) + 1);
  for (let i = 0; i < s.length; i++) if (cnt.get(s[i]) === 1) return i;
  return -1;
}

const encode = (strs) => strs.map((s) => s.length + '#' + s).join('');

function decode(str) {
  const res = [];
  let i = 0;
  while (i < str.length) {
    const hash = str.indexOf('#', i);
    const len = Number(str.slice(i, hash));
    res.push(str.slice(hash + 1, hash + 1 + len));
    i = hash + 1 + len;
  }
  return res;
}

function isPalindrome(s) {
  const ok = (c) => /[a-z0-9]/i.test(c);
  let l = 0, r = s.length - 1;
  while (l < r) {
    if (!ok(s[l])) l++;
    else if (!ok(s[r])) r--;
    else if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
    else { l++; r--; }
  }
  return true;
}

function lengthOfLongestSubstring(s) {
  const win = new Set();
  let l = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    while (win.has(s[r])) win.delete(s[l++]);
    win.add(s[r]);
    best = Math.max(best, r - l + 1);
  }
  return best;
}

function lengthOfLongestSubstring(s) {
  const last = new Map();
  let l = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    if (last.has(s[r]) && last.get(s[r]) >= l) l = last.get(s[r]) + 1;
    last.set(s[r], r);
    best = Math.max(best, r - l + 1);
  }
  return best;
}

function characterReplacement(s, k) {
  const cnt = new Array(26).fill(0);
  let l = 0, maxFreq = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    maxFreq = Math.max(maxFreq, ++cnt[s.charCodeAt(r) - 65]);
    while (r - l + 1 - maxFreq > k) cnt[s.charCodeAt(l++) - 65]--;
    best = Math.max(best, r - l + 1);
  }
  return best;
}

function checkInclusion(s1, s2) {
  if (s1.length > s2.length) return false;
  const need = new Array(26).fill(0), win = new Array(26).fill(0);
  const idx = (c) => c.charCodeAt(0) - 97;
  for (let i = 0; i < s1.length; i++) { need[idx(s1[i])]++; win[idx(s2[i])]++; }
  let matches = 0;
  for (let i = 0; i < 26; i++) if (need[i] === win[i]) matches++;
  for (let r = s1.length; r < s2.length; r++) {
    if (matches === 26) return true;
    for (const [c, d] of [[idx(s2[r]), 1], [idx(s2[r - s1.length]), -1]]) {
      if (win[c] === need[c]) matches--;
      win[c] += d;
      if (win[c] === need[c]) matches++;
    }
  }
  return matches === 26;
}