# [Java/C++] 6 lines solution - NO DP

• The idea is count the number of different palindromic substrings from their respective middle.

In the following code, when we consider the substring `s[i-j, ..., i+j]`, `i` is the middle index of the substring; When we consider the substring `s[i-1-j, ..., i+j]`, `(i-1, i)` is the middle index of the substring.

C++ version:

``````    int countSubstrings(string s) {
int res = 0, n = s.length();
for(int i = 0; i < n; i++){
for(int j = 0; i-j >= 0 && i+j < n && s[i-j] == s[i+j]; j++)res++; //substring s[i-j, ..., i+j]
for(int j = 0; i-1-j >= 0 && i+j < n && s[i-1-j] == s[i+j]; j++)res++; //substring s[i-1-j, ..., i+j]
}
return res;
}

``````

Java version:

``````    public int countSubstrings(String s) {
int res = 0, n = s.length();
for(int i = 0; i<n ;i++ ){
for(int j = 0; i-j >= 0 && i+j < n && s.charAt(i-j) == s.charAt(i+j); j++)res++; //substring s[i-j, ..., i+j]
for(int j = 0; i-1-j >= 0 && i+j < n && s.charAt(i-1-j) == s.charAt(i+j); j++)res++; //substring s[i-1-j, ..., i+j]
}
return res;
}
``````

• Interesting way to do it. Nice piece of code.

• @Vincent-Cai Is your solution a O(N^2) solution? I am not sure about that.

• @laro Yes, it is.

• Beautiful code, and easy to understand. Wonderful!

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