# Java solution, 8 lines, extendPalindrome

• Idea is start from each index and try to extend palindrome for both odd and even length.

``````public class Solution {
int count = 0;

public int countSubstrings(String s) {
if (s == null || s.length() == 0) return 0;

for (int i = 0; i < s.length(); i++) { // i is the mid point
extendPalindrome(s, i, i); // odd length;
extendPalindrome(s, i, i + 1); // even length
}

return count;
}

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

• @shawngao thank you for your answer. Could you please let us know the recursive relation that you used or if there was one? Thanks.

• 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 (when started from the middle element)? @shawngao

• Very smart solution, tks for sharing.

• Hey @shawngao think the if check at the start isnt required.
`if (s == null || s.length() == 0) return 0;`

• @shawngao thank you for your answer. Could you please let us know the recursive relation that you used or if there was none? Thanks.

I don't quite understand your question... You can find the detail explanation here https://leetcode.com/problems/longest-palindromic-substring/#/solution Approach #4 (Expand Around Center)

• Hey @shawngao think the if check at the start isnt required.
`if (s == null || s.length() == 0) return 0;`

It's a good habit to always do a sanity check at the beginning of your function unless explicitly told it's not necessary :)

• This post is deleted!

• This post is deleted!

• what's the time complexity? would the "worst" case be O(n^2)?

• @shawngao In the helper method, I used "if" instead of "while", and the solution became incorrect. Could you explain the reason why?

• worst

Hi, I have the same confusion with you? Have you already konw the answer?

• @FullLux
for the Time Complexity, I think the worst case should be O(n^2)

for example if we have an input as 'aaaa...aaaaa' (n times a)
then complexity in the helper function for each a should be:
1, 2, 3, ..., n/2, n/2, ..., 3, 2, 1

if we sum them up, it should be sth related to O(n^2)

• Similar idea but without global counter.

``````class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
N = len(s)
cnt = 0
for i in range(2 * N - 1):
pivot = float(i) / 2
left = int(floor(pivot))
right = int(ceil(pivot))
while left >= 0 and right < N and s[left] == s[right]:
cnt += 1
left -= 1
right += 1
return cnt
``````

• This post is deleted!

• @shawngao I wanted to ask how this solution is better than the naive, brute force solution (checking every possible substring)? I believe both solutions are O(n^2) time. Could someone provide some analysis on this?

• @theklam the time complexity of this kind of method is O(n^2), when the case is like "aaaa....aaaaa", however this is not often the case. when you use brute force, the time complexity is O(n^2) in whichever case, so that's the difference.

Actually, this method uses previous result (kind of like memorization, you will only calculate s(i, j) if s(i+1, j-1) is palindrome). While brute force didn't make good use of it.

• @WeiWeiJump I see. That makes sense. That's a good explanation. What do you think the runtime of this algorithm is then?

• @theklam you can answer that WORST CASE O(n^2), AVERAGE much less than that. Often the interviewer will ask you the worst case time complexity.

• This post is deleted!

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