MaiDeveloper

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
Mike Mai   Brooklyn, New York
I am full-stack web developer, passionate about building world class web applications. Knowledge in designing, coding, testing, and debugging. I love to solve problems.