Search code examples
javascriptfunctionrecursionpalindrome

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


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;
  }
}

Solution

  • 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"));