Counting Palindromes using recursion

Question

I currently have a code which counts the palindromes in a given string and it was working fine till I tested it with "appal" the function returned 0 when it should return 2 (appa and pp) I would really appreciate it if someone can edit my current code so that it meets that requirement, thank you! Here's my code:

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

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

  if (firstLetter === lastLetter) {
    let stringWithoutFirstAndLastLetters = string.substring(1, string.length - 1);
    return countPalindromes(stringWithoutFirstAndLastLetters, count + 1);
  } else {
    return 0;
  }
}

console.log(countPalindromes("kayak", 0));
console.log(countPalindromes("aya", 0));
console.log(countPalindromes("appal", 0));

I think your problem is that you would only ever check whether `appal` and `ppa` are palindromes. You'll need to find some way to check the string without ONLY the first letter and the string without ONLY the last letter. — M-Chen-3, Nov 12 '20 at 01:35
Should `xyzappa` also return 2 because `appa` and `pp` are palindromes? How exactly is this supposed to work? — Sylwester, Nov 12 '20 at 02:49
yes that should return 2 as well, my assignments asks me to "Given a string, calculate the amount of palindromes that exist within that string (single letters excluded), whilst using recursion" @Sylwester — 28spaceaddict, Nov 12 '20 at 02:56
If you click on the palindrome tag at the bottom of your question, you'll see that there are 1426 questions already asked about palindromes on Stack Overflow. Did none of those answer your question? — Heretic Monkey, Nov 16 '20 at 12:47

Candace Ahrends · Answer 1 · 2020-11-12T06:10:36.457

0

function isPalindrome(str) {
  return str == str.split("").reverse().join("");
}
//iterative only solution
function countPalindromes(s) {
  let count = 0;
  for (let i = 0; i < s.length - 1; i++) {
    const sub = s.slice(i);

    for (let j = 2; j < sub.length + 1; j++) {
      if (isPalindrome(sub.slice(0, j))) {
        count++
      }
    }
  }
  return count;
}

console.log(countPalindromes("kayak"));
console.log(countPalindromes("aya"));
console.log(countPalindromes("appal"));

You are comparing the first letter with the last letter and will return zero because this will be false for appal yet true for the other 2 test cases.

edited Nov 12 '20 at 06:10

answered Nov 12 '20 at 01:34

Candace Ahrends

86
1
3

would you be able to help me fix that please? @candaceahrends – 28spaceaddict Nov 12 '20 at 01:39
Here is a similar question: https://stackoverflow.com/questions/64596115/how-to-count-all-the-palindromes-in-a-string-using-recursion – Candace Ahrends Nov 12 '20 at 03:06
that question talks about implementing an iterative function and it has the same problem where appal returns 0 instead of 2 @candaceahrends – 28spaceaddict Nov 12 '20 at 03:10
my assignments asks me to "Given a string, calculate the amount of palindromes that exist within that string (single letters excluded), whilst using recursion" @CanadaceAhrends – 28spaceaddict Nov 12 '20 at 03:10
please help me, i would really appreciate it – 28spaceaddict Nov 12 '20 at 03:18

tonitone120 · Accepted Answer · 2020-11-16T12:43:07.330

0

I think this function does the trick. Happy to refactor and explain it later. I'd rather write a new function because I don't think your code is close to executing the task.

function returnNumberOfPalindromes(word) {
    function isPalindrome(chunk) { 
        return [...chunk].reverse().join('') === chunk;
    }
    let tally = 0;
  
    for (let index1 = 0; index1 <= word.length; index1++) {
      for (index2 = index1 + 2; index2 <= word.length; index2++) { 
        let chunk = word.slice(index1, index2); 
        if (isPalindrome(chunk)) {
            tally += 1;
        };
      }
    }
    console.log(tally);
}

returnNumberOfPalindromes("kayak");
returnNumberOfPalindromes("aya");
returnNumberOfPalindromes("appal");
returnNumberOfPalindromes("addadaadd");

edited Nov 16 '20 at 12:43

answered Nov 12 '20 at 03:47

tonitone120

1,920
3
8
25

do you have an idea of how i can code the same thing from an iterative approach? @tonitone120 – 28spaceaddict Nov 12 '20 at 03:55
@28spaceaddict I understand the word iterative to mean 'repeating' - for example, a `for loop`. (By that definition, I'd say my answer is an iterative approach). Can you give an example of what you mean by iterative approach? I have to go now but I will be back later – tonitone120 Nov 12 '20 at 03:59
yup that's an iterative approach so I need the same code with an iterative approach and also by using recursion @tonitone120 – 28spaceaddict Nov 12 '20 at 04:03
do you think you'll be back in 20 mins because I have to submit it in 40 mins? – 28spaceaddict Nov 12 '20 at 04:03

score 0 · Answer 3 · answered Nov 12 '20 at 13:01

So basically if you find a palindrome like pp or apa by scanning the string and comparing the current with current+1 and current+2 in an iterative loop and storing the matches as objects with start end end index.
You initiate a count which is the length of the array.
Update the array by filter the elements where you update the object with one less and one more for start end if the 1 larger is a palindrome and return true or return false and get it removed.
if the array is length zero you return the count
add the array length to the count and repeat from 3.

@28spaceaddict Since this most certainly is homework I won't. You should write your own code. My answer just describes how I would have done it. If you read this and do it manually on paper, do you see any weaknesses with it? — Sylwester, Nov 12 '20 at 15:19

Counting Palindromes using recursion

3 Answers3

Linked