Leetcode 647: Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/description/

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".

Note:

1. The input string length won't exceed 1000.

Notes:

This question asks for all the palindromic substrings. So what we need to do is to develop an effective way to count them, and at the same time to avoid repeating count.

There are two types of strings: one is with size of odd number; the other one is with size of even number.

So at position i, we can choose:

1: choose s[i] as the center element, the final size is odd;

2: choose s[i-1] and s[i] as the center elements, the final size is even.

See the code below:

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0, len = s.size();
        for(int i=0; i<len; ++i) {
            ++res;
            int j = 1;
            while(i-j >=0 && i+j <len && s[i-j] == s[i+j]) {
                ++res;
                ++j;
            }
            if(i-1>=0) {
                int j = 0;
                while(i-1-j >=0 && i+j <len && s[i-1-j] == s[i+j]) {
                    ++res;
                    ++j;
                }
            }
        }
        return res;
    }
};