Palindromes, Permutations, Anagrams | Skilled.dev
Learn

Palindromes, Permutations, Anagrams

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
Loading...

What makes strings unique is that there is a limited set of characters (eg. 26 in the English alphabet), and their order and number of times a character appears creates conveys meaning. For string interview questions, it's very common to test on this through palindromes, permutations, and anagrams. Having an understanding of what these terms mean before going in can help make you feel comfortable diving into a problem.

Palindromes

A palindrome is a word, phrase, or sequence of characters that is the same forward as it is backward.

Examples of palindromes include:

pop

level

racecar

Never odd or even // ignore white space and case

To check for a palindrome, we can do the following:

// Regex to remove non-alphanumeric
const removeNonAlphanumeric = string => string.replace(/[^0-9a-z]/gi, '');

const isPalindrome = string => {
  // For simplicity, I'm doing the transforming here at an assumed O(n) cost
  // You could also not transform it and consider this when you compare characters
  const formattedString = removeNonAlphanumeric(string).toLowerCase();

  // Walk from the beginning and end to the middle and compare each character
  for (let i = 0; i < formattedString.length / 2; i++) {
    // If the characters are ever not equal, it's not a palindrome
    if (formattedString[i] !== formattedString[string.length - 1 - i]) {
      return false;
    }
  }

  return true;
};

Permutations

A permutation is different ordering of a string's characters.

For example, a 3 letter word will have 6 (3! = 3 * 2 * 1) permutations. Consider the word dev:

1. dev
2. dve
3. evd
4. edv
5. vde
6. ved

If a question asks if strings are permutations of each other, it is asking if they have the same characters in a different order.

Anagrams

An anagram is a word or phrase that when rearranged will create a new word or phrase. For example silent and listen are anagrams of each other.

You may think anagrams and permutations look similar to each other, and you would be right. All anagrams are permutations of each other, but not all permutations are anagrams. By definition an anagram must have meaning (be a real word or phrase), but a permutation can be any ordering of the characters without needing to have meaning.

However, interviews often use the terms anagram and permutation interchangeably, and if the question asks for anagrams, it may not specifically require that the words have meaning.

Prev
Strings
Next
Group Permutations of Palindromes
Loading...

Table of Contents