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

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

• javascript

• Print the strings you find, and you should see the problem? – Fuhrmanator Commented Nov 12, 2017 at 19:58
• If the characters can be bined in any order you first need all permutations. You are only working from left to right – charlietfl Commented Nov 12, 2017 at 20:07
• @charlietfl I assumed that because I was reversing the string as I iterated through that this wouldn't matter, or is this not the case? – Matt Kent Commented Nov 12, 2017 at 20:27
• Depends on the constraints of the assignment. – charlietfl Commented Nov 12, 2017 at 20:30

2 Answers 2

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

function soln(inp){
    const op = []
    for(let i=0; i<input.length; i++){
        for(let j=i; j<=input.length; j++){
            let innerInp = input.substring(i,j)
            if(innerInp.length > 1 && (innerInp === innerInp.split('').reverse().join(''))){
                op.push(innerInp);
            }
        }
    }
   return op.length
};