Dynamic Programming Java Solution Memoization with explanation
We make a grid with rows = length of string2 and columns = length= string1\nIf the charecters in string 1 and string 2 differ we increment the existing count.\n
We make a grid with rows = length of string2 and columns = length= string1\nIf the charecters in string 1 and string 2 differ we increment the existing count.\nIf the charecters in string 1 and string 2 are similar , we check for substrings to the left and right that differ by 1 .\n\n\nTest Case :\n"bbbbb"\n"abbab"\nMemoisation table of rows = string1.length() and columns = string2.length()\n```\n\t\t a    b   b    a    b\n\tb\t1     3   5    6    6 \n\tb\t7    10   12   13  14 \n\tb\t15   17   20   21  22 \n\tb\t23   24   26   27  28 \n\tb\t29   30   31   32  33 \n```\n\n```\nclass Solution {\n    public int countSubstrings(String s, String t) {\n        int[][] mapping = new int[s.length()][t.length()];\n        for(int i=0; i< s.length(); i++){\n            if(i!=0){\n                mapping[i][0]=mapping[i-1][t.length()-1] ;\n            }\n            for(int j=0; j< t.length() ;j++  )     {               \n                if(  s.charAt(i) != t.charAt(j) ){\n                    if(j!=0){\n                        mapping[i][j]=1+ mapping[i][j-1];\n                    }else{\n                        mapping[i][j]=1+mapping[i][j];\n                    }\n                    \n                }else{\n                  int left_s = i-1;\n                  int right_s= i+1;\n                  int left_t = j-1;\n                  int right_t = j+1;\n                  int add_val=0;  \n\t\t\t\t  // checking substrings to the left that differ by one character\n                  while(left_s >= 0  && left_t >=0  ){\n    \n                      if(s.charAt(left_s)!= t.charAt(left_t)){\n                          add_val++;\n                          \n                          break;\n                      }\n                      left_s--;\n                      left_t--;\n                  }\n\t\t\t\t    // checking substrings to the right that differ by one character\n                  while(right_s < s.length()  && right_t < t.length()  ){\n                   \n                      if(s.charAt(right_s)!= t.charAt(right_t)){\n                          add_val++;\n                          right_s++;\n                          right_t++;\n\t\t\t\t\t\t  // checking substrings which contain the given substring and not differ by 1\n                          while( right_s < s.length()  && right_t < t.length() && s.charAt(right_s)==t.charAt(right_t) ){\n                              add_val++;\n                              right_s++;\n                              right_t++;\n                          }\n                          break;\n                      }\n                      right_s++;\n                      right_t++;\n                  }  \n                    \n                    if(j!=0){\n                        mapping[i][j]=add_val+ mapping[i][j-1];\n                    }else{\n                        mapping[i][j]=add_val+mapping[i][j];\n                    }  \n                    \n                }\n            }\n        }\n        \n        return mapping[s.length()-1][t.length()-1];\n    }\n}\n\n
[]