Calculate how many sub-strings of a string are palindromes

I'm currently trying to work out how many substrings of a given string are palindromes.

When given the string aabaa the expected output is 5 however my code outputs 4. I'm not too sure why, can any one help me solve this?

My code:

function countPalindromesInString(s) {
    let count = 0;

    if (s === s.split('').reverse().join('')) {
        count += 1;
    }

    let testStr = '';
    for (let i = 0; i < s.length; i++) {
        testStr += s[i];

        if (testStr === testStr.split('').reverse().join('')) {
            count += 1;
        }
    }
    return count;
}

1 answer

  • answered 2017-11-12 20:31 Dragos

    I'm not sure why you expect output 5 for input aabaa. From my point of view, if you consider a single letter as a palindrome than the output should be 9, otherwise the result should be 4: "aa", "aa", "aba", "aabaa". Your code only count from left to right and also double counts the full 5 letter string, once in the beginning, here:

    if (s === s.split('').reverse().join('')) { count += 1; }

    and once in the for loop for case i=4;

    Here is a solution to your question:

    function countPalindromesInString(s) {
        let count = 0;  //or s.length if you chose to count single letters as palindrome
        let subString;
    
        for (let i = 1; i < s.length; i++) {
          for(let j = 0; j < s.length - i; j++) {
            subString = s.substring(j, j+i+1);
            if(subString === subString.split('').reverse().join('')) {
                count += 1;
            }
          }
        }
        return count;
    }
    

    Later Edit:

    If we want to count unique palindromes in your string, we can store the palindromes found in an array and every time we find another one, we check if it was previously added:

    function countPalindromesInString(s) {
        let subStrings = [];
    
        for (let i = 0; i < s.length; i++) {
          for(let j = 0; j < s.length - i; j++) {
            let subString = s.substring(j, j+i+1);
            if(subString === subString.split('').reverse().join('') && !subStrings.includes(subString)) {
              subStrings.push(subString);
            }
          }
        }
        return subStrings.length;
    }