 # Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

``````Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
``````

Example 2:

``````Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
``````

### Solution

``````/**
* Palindromic String
* @param {string} s
* @return {number}
* @time complexity: O(n^2) where n is the length of s, in each iteration it might do O(n) work
* @space complexity: O(1)
*/
function palindromicString(s) {
let count = 0;

for (let i = 0; i < s.length; i++) {
count += expandFromCenter(s, i, i);     // Handle odd palindrome like aba
count += expandFromCenter(s, i, i + 1); // Handle even palindrome like abba
}

return count;
};

/**
* Expand from Center
* @param {string} s
* @param {number} left
* @param {number} right
* @return {number} the maximum number of characters that can be form a palindrome
* @time complexity: O(n)
* @space complexity: O(1)
*/
function expandFromCenter(s, left, right) {
let count = 0;

while (left >= 0 && right < s.length && s.charAt(left) === s.charAt(right)) {
count++;
left--;
right++;
}

return count;
}
``````

### Test Case

``````const assert = require('chai').assert;

describe('Palindromic Substrings', () => {

it('should return 3 when \'abc\' is given', () => {
assert.strictEqual(palindromicString('abc'), 3);
});

it('should return 6 when \'aaa\' is given', () => {
assert.strictEqual(palindromicString('aaa'), 6);
});

it('should return 0 when \'\' is given', () => {
assert.strictEqual(palindromicString(''), 0);
});

it('should return 1 when \'a\' is given', () => {
assert.strictEqual(palindromicString('a'), 1);
});

});
``````
``````  Palindromic Substrings
✓ should return 3 when 'abc' is given
✓ should return 6 when 'aaa' is given
✓ should return 0 when '' is given
✓ should return 1 when 'a' is given

4 passing (13ms)
`````` Mike Mai   Brooklyn, New York
I am a full-stack web developer. I love to learn cutting-edge technology and solve problems. I also like photography and graphic designs.