Palindromic Substrings

Problem

Given a string s, return the number of substrings within s that are palindromes.

A palindrome is a string that reads the same forward and backward.

Examples

Example 1:

Input: s = "abc"

Output: 3

Explanation: “a”, “b”, “c”.

Example 2:

Input: s = "aaa"

Output: 6

Explanation: “a”, “a”, “a”, “aa”, “aa”, “aaa”. Note that different substrings are counted as different palindromes even if the string contents are the same.

Constraints

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

You should aim for a solution as good or better than O(n^2) time and O(1) space, where n is the length of the given string.

Solution

Every index is the middle of a palindrome. We use 2 pointer walking, and need to consider both even and odd lengths.

class Solution {
public:
    int countSubstrings(string s) {
        int count = 0;
        for (int i = 0; i < s.size(); ++i) {
            // Odd 
            int l = i;
            int r = i;
            while (l >= 0 && r < s.size() && s[l] == s[r]) {
                ++count;
                --l;
                ++r;
            }
            // Even
            l = i;
            r = i + 1;
            while (l >= 0 && r < s.size() && s[l] == s[r]) {
                ++count;
                --l;
                ++r;
            }
        }
        return count;
    }
};