class Solution { public int countSubstrings(String s) { /* question of DP gap strategy vid 32 of dp playlist 1)making a boolean array for checking pallindrome by keeping start points on coloumn and end points on rows 2)travelling the upper triangle only ,where 0th diagnol represents substring with 0 gap that is that element itself 3) handling for 0 ,1 gap which are trivial case then handling for 2 onwards , where we will check extremities and if inside string is also pallindrome by checking diagnolly behind */ //1 boolean dp[][] = new boolean[s.length()][s.length()]; int count = 0 , n = s.length(); //2 for(int gap = 0 ; gap < n ; gap ++){ //every diagnol ends at last coloumn,so this loop runs from first //row till last coloumn for(int i = 0 , j = gap ; j < n ; i++ , j++){ //handling for 0 gap diagnol -> all are true if(gap == 0 ){ dp[i][j] = true; count++; } //handling for 1 gap diagnol -> check if both chars are equal else if(gap == 1){ if(s.charAt(i) == s.charAt(j)){ dp[i][j] = true; count++; } } //3 else{ if(s.charAt(i) == s.charAt(j) && dp[i+1][j-1] == true){ dp[i][j] = true; count++; } } } } return count; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter