Anagrams & Palindromes

Anagrams and palindromes are two of the most common string families in coding interviews. They look different on the surface but both reduce to questions about character frequencies and symmetry — two ideas you already know how to encode efficiently.

Detecting Anagrams

Two strings are anagrams if one is a rearrangement of the other — they contain the exact same characters with the same frequencies.

There are two common approaches:

Approach	Time	Space	When to use
Sort both strings, compare	O(n log n)	O(n)	Simple, fine for most interviews
Frequency array / Map	O(n)	O(1) for fixed alphabet	When performance matters

// Approach 1 — Sort (O(n log n))
function isAnagramSort(s, t) {
  if (s.length !== t.length) return false;
  return s.split('').sort().join('') === t.split('').sort().join('');
}

// Approach 2 — Frequency array (O(n), O(1) space for lowercase a-z)
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const freq = new Array(26).fill(0);
  const a = 'a'.charCodeAt(0);
  for (let i = 0; i < s.length; i++) {
    freq[s.charCodeAt(i) - a]++;
    freq[t.charCodeAt(i) - a]--;
  }
  return freq.every(n => n === 0);
}

console.log(isAnagram('listen', 'silent')); // true
console.log(isAnagram('anagram', 'nagaram')); // true
console.log(isAnagram('rat', 'car'));          // false

Note

LeetCode 242 — Valid Anagram. Follow-up: "what if inputs contain Unicode?" Use a Map instead of a fixed-size array.

Group Anagrams

Given an array of strings, group all anagrams together (LeetCode 49).

The key insight: anagrams are identical when sorted. Sort each string to get its canonical form, then use that as a Map key to bucket the originals.

function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const key = s.split('').sort().join('');
    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·k) alternative — encode frequency as the key
function groupAnagramsFast(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('#');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}

Tip

The frequency-key approach is O(n·k) vs O(n·k log k) for sorting, where k is average string length. Prefer it when strings are long.

Valid Palindrome — Two Pointers

A string is a palindrome if it reads the same forwards and backwards. The two-pointer approach checks this in O(n) time and O(1) space by comparing characters from both ends moving inward.

// LeetCode 125 — also ignores non-alphanumeric and is case-insensitive
function isPalindrome(s) {
  const isAlNum = ch => (ch >= 'a' && ch <= 'z')
                     || (ch >= '0' && ch <= '9');
  let left = 0, right = s.length - 1;

  while (left < right) {
    while (left < right && !isAlNum(s[left].toLowerCase()))  left++;
    while (left < right && !isAlNum(s[right].toLowerCase())) 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

// LeetCode 680 — Valid Palindrome II: allow one deletion
function validPalindromeII(s) {
  function isPalin(lo, hi) {
    while (lo < hi) {
      if (s[lo] !== s[hi]) return false;
      lo++; hi--;
    }
    return true;
  }
  let l = 0, r = s.length - 1;
  while (l < r) {
    if (s[l] !== s[r]) {
      // try skipping s[l] or s[r]
      return isPalin(l + 1, r) || isPalin(l, r - 1);
    }
    l++; r--;
  }
  return true;
}

console.log(validPalindromeII('abca')); // true (remove 'c' or 'b')

Palindromic Substrings — Expand Around Center

Every palindrome has a center. For odd-length palindromes the center is a single character; for even-length palindromes it lies between two identical adjacent characters.

The expand-around-center technique tries every possible center in O(n) iterations, expanding outward while the characters match — O(n) centers × O(n) expansion = O(n²) total.

// LeetCode 647 — count all palindromic substrings
function countSubstrings(s) {
  let count = 0;

  function expand(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      count++;
      left--;
      right++;
    }
  }

  for (let i = 0; i < s.length; i++) {
    expand(i, i);     // odd-length palindromes (center at i)
    expand(i, i + 1); // even-length palindromes (center between i and i+1)
  }
  return count;
}

console.log(countSubstrings('abc'));  // 3  ('a', 'b', 'c')
console.log(countSubstrings('aaa'));  // 6  ('a','a','a','aa','aa','aaa')

Longest Palindromic Substring

Find the longest palindromic substring in a string (LeetCode 5).

The same expand-around-center technique applies — just track the best start/end seen so far. This is O(n²) time, O(1) space, and fast enough for n ≤ 1000.

function longestPalindrome(s) {
  let start = 0, maxLen = 1;

  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      if (r - l + 1 > maxLen) {
        start = l;
        maxLen = r - l + 1;
      }
      l--; r++;
    }
  }

  for (let i = 0; i < s.length; i++) {
    expand(i, i);     // odd
    expand(i, i + 1); // even
  }
  return s.slice(start, start + maxLen);
}

console.log(longestPalindrome('babad'));  // 'bab' or 'aba'
console.log(longestPalindrome('cbbd'));   // 'bb'
console.log(longestPalindrome('racecar')); // 'racecar'

Manacher's Algorithm — O(n)

Manacher's algorithm finds the longest palindromic substring in O(n) time using the key observation: if we already know a palindrome centred at c that extends to position r, then for any centre i inside [c-r, r], the palindrome radius at i is at least as large as its mirror across c — as long as we stay inside the known boundary.

The standard trick is to insert a sentinel character (e.g. '#') between every character so that odd and even cases unify. Then maintain a rightmost boundary and its centre.

function manacher(s) {
  // Transform: "abc" → "#a#b#c#"
  const t = '#' + s.split('').join('#') + '#';
  const n = t.length;
  const p = new Array(n).fill(0); // p[i] = palindrome radius at i in t
  let centre = 0, right = 0;

  for (let i = 0; i < n; i++) {
    const mirror = 2 * centre - i;
    if (i < right) p[i] = Math.min(right - i, p[mirror]);

    // expand around i
    while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n
           && t[i - p[i] - 1] === t[i + p[i] + 1]) {
      p[i]++;
    }

    // update rightmost boundary
    if (i + p[i] > right) {
      centre = i;
      right  = i + p[i];
    }
  }

  // Find the maximum radius and map back to original string
  let maxLen = 0, centreIdx = 0;
  for (let i = 0; i < n; i++) {
    if (p[i] > maxLen) { maxLen = p[i]; centreIdx = i; }
  }
  const start = (centreIdx - maxLen) / 2;
  return s.slice(start, start + maxLen);
}

console.log(manacher('babad'));   // 'bab'
console.log(manacher('cbbd'));    // 'bb'
console.log(manacher('racecar')); // 'racecar'

Note

Manacher's is O(n) time and space. It is rarely required in interviews — the expand-around-center O(n²) solution is almost always acceptable. Know Manacher's to impress, but do not start with it.

Complexity Summary

Problem	Best Algorithm	Time	Space
Valid Anagram	Frequency array	O(n)	O(1)
Group Anagrams	Frequency-key Map	O(n·k)	O(n·k)
Valid Palindrome	Two pointers	O(n)	O(1)
Count Palindromic Substrings	Expand around center	O(n²)	O(1)
Longest Palindromic Substring	Expand around center	O(n²)	O(1)
Longest Palindromic Substring (optimal)	Manacher's	O(n)	O(n)

Practice Problems

LeetCode 242 — Valid Anagram
LeetCode 49 — Group Anagrams
LeetCode 438 — Find All Anagrams in a String (sliding window)
LeetCode 125 — Valid Palindrome
LeetCode 680 — Valid Palindrome II (one deletion allowed)
LeetCode 647 — Palindromic Substrings (count all)
LeetCode 5 — Longest Palindromic Substring
LeetCode 132 — Palindrome Partitioning II (DP + palindrome check)