# Java O(n^2) time O(1) space solution with comments.

• ``````public int countSubstrings(String s) {
int sum = 0;
// Loop across different middle points.
for (int i = 0; i < s.length(); i++) {
// Find all odd length palindrome with i as middle point.
sum += findPalindromic(s, i, i);
// Find all even length palindrome with i and i+1 as middle point.
sum += findPalindromic(s, i, i + 1);
}
return sum;
}

// Expend from the current mid point to all of its low and high positions.
private int findPalindromic(String s, int left, int right) {
int count = 0;
// Increase count if the substring is a validate palindrome.
while (left >= 0 && right < s.length() && s.charAt(left--) == s.charAt(right++))
count++;
return count;
}
``````

• @xiyunyue2 thank you for your answer. Could you kindly share the recursive equation that you used? Or, was there none?

• Also, was the intuition of working with the middle element (`i`) because of the fact that the left and right parts of a palindrome are same?

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.