Palindromic Substrings

Problem

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

Brute Force: O(n^2)

public class Solution {
    public int countSubstrings(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                if (isPalindrome(s.substring(i, j))) res++;
            }
        }
        return res;
    }

    private boolean isPalindrome(String s) {
        int start = 0, end = s.length() - 1;
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--)) return false;
        }
        return true;
    }
}

Optimal Solution by Checking Sides

public class Solution {
    int res = 0;
    public int countSubstrings(String s) {
        for (int i = 0; i < s.length() - 1; i++) {
            check(s, i, i);
            check(s, i, i + 1);
        }
        return res + 1;
    }

    private void check(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
            res++;
        }
    }
}

Analysis

The brute force solution checks from the start index with every possible length
The optimal solution checks from the start index, and then go to two sides
Because the substring can have odd and even length, we call helper method with i, i and i, i + 1
At the end, we return res + 1 because of counting the last character