# simple O(N^2) time O(N) space DP solution

• NxN space solution is self explained as below. we could safely reduce space to 2*n by using two rows to mimic all imaginary rows in 2d solution. the trick is to mod the rowIndex.

``````/**
s(i,j) is a palindrome, only when s(i-1,j+1) is a palindrome and s[i]==s[j]. special cases include, i=j and i=j+1
**/
public int countSubstrings2D(String s) {
if(s==null||s.length()==0) return 0;
int n=s.length();
boolean[][] dp=new boolean[n][n];
int countOfTrues=0;
for(int i=n-1;i>=0;i--){
for(int j=i;j<n;j++){
dp[i][j]=(s.charAt(i)==s.charAt(j))&&(j<i+2||dp[i+1][j-1]);
if(dp[i][j]) countOfTrues++;
}
}
return countOfTrues;
}
/*
reduce to 1-D space
*/
public int countSubstrings1D(String s) {
if(s==null||s.length()==0) return 0;
int n=s.length();
boolean[][] dp=new boolean[2][n];
int countOfTrues=0;
for(int i=n-1;i>=0;i--){
for(int j=i;j<n;j++){
// use 2 rows to swap to save spaces
int curRow=i%2;
int preRow=(i+1)%2;
dp[curRow][j]=(s.charAt(i)==s.charAt(j))&&(j<i+2||dp[preRow][j-1]);
if(dp[curRow][j]) countOfTrues++;
}
}
return countOfTrues;
}
``````

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