How to count all the palindromes in a string using recursion?

Question

I have a recursive function that checks if a string is a palindrome, but my assignment asks me to count the number of palindromes in a string (for example kayak has 2).

I'm really confused about how I can implement a recursive function that counts the number of palindromes. Here's my current code:

function isPalindrome(string) {
  if (string.length <= 1) {
    return true;
  }

  let [ firstLetter ] = string;
  let lastLetter = string[string.length - 1];

  if (firstLetter === lastLetter) {
    let stringWithoutFirstAndLastLetters = string.substring(1, string.length - 1);
    return isPalindrome(stringWithoutFirstAndLastLetters);
  } else {
    return false;
  }
}

Answer 1

When the function gets a palindrome it is easy:

1. Record the input
2. Try again without the edges
3. Stop when input is three characters or less

"kayak" -> "aya"

If the input isn't a palindrome try "both ends" recursively e.g. with "kayam" try with both "kaya" and "ayam" and keep going...

We stop the recursion when a string is 3 (or less) characters. A single character is not a palindrome and checking whether a two or three characters string is a palindrome is trivial.

                      kayam
                        |
                  +-------------+
                  |             |
                 kaya          ayam
                  |             |
              +-------+     +--------+
              |       |     |        |
             kay     aya   aya      yam

---

const reverse =
  ([...xs]) =>
    xs.reverse().join("");

const is_palindrome =
  a =>
      a.length === 1  ? false
    : a.length <= 3   ? a[0] === a[a.length-1]
                      : a === reverse(a);

const find_palindromes = str => {
  const scan =
    (x, xs = []) =>
        x.length <= 3     ? xs.concat(is_palindrome(x) ? x : [])
      : is_palindrome(x)  ? xs.concat
                              ( x
                              , scan(x.slice(1, -1))
                              )
                          : xs.concat
                              ( scan(x.slice(0, -1))
                              , scan(x.slice(1))
                              );

  return [...new Set(scan(str))];
};


console.log(find_palindromes("kayak").join());
console.log(find_palindromes("kayakkayak").join());
console.log(find_palindromes("kayakcanoe").join());
console.log(find_palindromes("kayam").join());
console.log(find_palindromes("appal").join());
console.log(find_palindromes("madamimadam").join());
console.log(find_palindromes("madamimadamkayak").join());

Answer 2

I think the accepted answer does not actually work. It will not count palindromes unless they are centered in the string and will count substrings that are not palindromes if as long as they start and end with the same letter. The answer from CertainPerformance would probably work but I think it would result in checking a lot of strings that don't need to be checked. Here's what I came up with, I think it works for the extra tests I've added.

function countPalindromes(string) {
    if (string.length <= 1) {
    return 0;
    }

    count = 0

    for ( var i = 0; i < string.length; i++  ) {
    count += countPalindromesCenteredAt(string, i)
    count += countPalindromesCenteredAfter(string, i)
    }

    return count
}

function countPalindromesCenteredAt(string, i) {
    count = 0
    for ( var j = 1; i-j>=0 && i+j < string.length; j++  ) {
    if (string.charAt(i-j) === string.charAt(i+j)) {
        count += 1
    }
    else {
        return count
    }
    }

    return count
}

function countPalindromesCenteredAfter(string, i) {
    count = 0
    
    for ( var j = 1; i-j>=0 && i+j < string.length; j++  ) {
    if (string.charAt(i-j+1) === string.charAt(i+j)) {
        count += 1
    }
    else {
        return count
    }
    }

    return count
}

console.log(countPalindromes("kayak"));
console.log(countPalindromes("aya"));
console.log(countPalindromes("kayakcanoe"));
console.log(countPalindromes("kcanoek"));

Answer 3

One method would be to first get all substrings, then validate each:

getAllSubstrings('kayak').filter(str => str.length >= 2 && isPalindrome(str))

function getAllSubstrings(str) {
  var i, j, result = [];

  for (i = 0; i < str.length; i++) {
      for (j = i + 1; j < str.length + 1; j++) {
          result.push(str.slice(i, j));
      }
  }
  return result;
}
function isPalindrome(string) {
  if (string.length <= 1) {
    return true;
  }

  let [ firstLetter ] = string;
  let lastLetter = string[string.length - 1];

  if (firstLetter === lastLetter) {
    let stringWithoutFirstAndLastLetters = string.substring(1, string.length - 1);
    return isPalindrome(stringWithoutFirstAndLastLetters);
  } else {
    return false;
  }
}
console.log(
  getAllSubstrings('kayak').filter(str => str.length >= 2 && isPalindrome(str))
);

Answer 4

Here's an answer similar to that from CertainPerformance, but using recursion for the helper functions:

const getSubstrings = (str) =>
  str .length == 0 
    ? []
    : [
        ... str .split ('') .map ((_, i) => str .slice (0, str .length - i)),
        ... getSubstrings (str .slice (1))
      ]

const isPalindrome = (str) =>
  str .length < 2
    ? true
    : str [0] === str .slice (-1) [0] && isPalindrome (str .slice (1, -1))

const getPalindromicSubstrings = (str) =>
  getSubstrings (str) 
    .filter (s => s.length > 1) 
    .filter (isPalindrome)

const countPalindromicSubstrings = (str) =>
  getPalindromicSubstrings (str) .length

const countUniquePalindromicSubstrings = (str) =>
  new Set(getPalindromicSubstrings (str)) .size

console .log (getPalindromicSubstrings ('madamimadam'))
console .log (countPalindromicSubstrings ('madamimadam'))
console .log (countUniquePalindromicSubstrings ('madamimadam'))

.as-console-wrapper {max-height: 100% !important; top: 0}

• getSubstrings does just what you'd expect. getSubstrings('abcd') returns ["abcd", "abc", "ab", "a", "bcd", "bc", "b", "cd", "c", "d"].

• isPalindrome says that the empty string and single-character strings are automatically palindromes and that for another string we check that the two end characters match, recurring on the remainder.

• getPalindromicSubstrings finds all the substrings that are palindromes, skipping those of length 1.

• countPalindromicSubstrings returns a count of those.

• countUniquePalindromicSubstrings uses a Set to filter out duplicates and returns that count.

We could also easily write a getUniquePalindromicSubstrings in a similar manner if needed.

getSubstrings is the only function with any complexity. It operates by repeatedly slicing our string from to a value varying from length down to 1, then recurring on the string starting with the second character, stopping when our input is empty.