palindromic.java

 
    public boolean[][] allSubstrings(String S) {
        int N = S.length();
        int count=0;
        boolean [][] dp = new boolean [N][N];
        for(int i=0;i<N;i++){
            dp[i][i] = true;
            count++;
            if(i+1<N && S.charAt(i)==S.charAt(i+1)) {
                dp[i][i+1] = true;
                count++;
            }
        }
        
        for(int len=3;len<=N;len++){
            for(int i=0, j=i+len-1; j<N; i++, j++){
                if(S.charAt(i)==S.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1];
                }  
                if(dp[i][j]) {
                    count++;
                }
            }
        }
        
        return dp;
    }
    
    public boolean isPalindrom(int l, int r) {
      return dp[l][r];
    }
}