Java Easy Dp recursion solution with explanation
The idea behind this solution is:\nthere can be two cases:\n1) Case 1 : both characters are same --> If both characters are same this means we need to look for 
The idea behind this solution is:\nthere can be two cases:\n1) Case 1 : both characters are same --> If both characters are same this means we need to look for one character which is different. If we get the differnet character then in following iterations look only for same characters, if you encounter the one more different character again then it means we encounter two different characters, in this case there is no point on going more further so simply return 0.. This is exactly implemented in first if case i.e.\n```\nif(isSame == 1) {\n            if(a.charAt(i) != b.charAt(j)) {\n            dp.put(key,0);\n            return dp.get(key);\n            } else {\n             dp.put(key, 1 + findMaximumSubstr(i+1,j+1,1, dp,a, b));\n            return dp.get(key);\n            }\n        } \n```\n\n2) Case 2 : When both characters are different, then look only for similiar characters. The code is as follows:\n```\nif(isSame == 0) {\n            dp.put(key, (a.charAt(i) != b.charAt(j) ? 1 : 0) + findMaximumSubstr(i+1,j+1,(a.charAt(i) != b.charAt(j) ? 1 : 0),dp, a, b));\n            return dp.get(key);\n        }\n```\n\n\nComplete code is as follows:\n\t\t\n```\nclass Solution {\n    String createDpKey(int i, int j, int k) {\n        return Integer.toString(i) + "_" + Integer.toString(j) + "_" + Integer.toString(k);\n    }\n    int findMaximumSubstr(int i, int j, int isSame, Map<String,Integer> dp, String a, String b) {\n        if(i >= a.length() || j >= b.length()) return 0;\n        String key = createDpKey(i,j,isSame);\n        if(dp.containsKey(key)) return dp.get(key);\n        if(isSame == 1) {\n            if(a.charAt(i) != b.charAt(j)) {\n            dp.put(key,0);\n            return dp.get(key);\n            } else {\n             dp.put(key, 1 + findMaximumSubstr(i+1,j+1,1, dp,a, b));\n            return dp.get(key);\n            }\n        } else if(isSame == 0) {\n            dp.put(key, (a.charAt(i) != b.charAt(j) ? 1 : 0) + findMaximumSubstr(i+1,j+1,(a.charAt(i) != b.charAt(j) ? 1 : 0),dp, a, b));\n            return dp.get(key);\n        }\n             return 0;   \n    }\n    public int countSubstrings(String a, String b) {\n        Map<String,Integer> dp = new HashMap<>();\n        int ans = 0;\n        for(int i = 0 ;i < a.length(); i++)\n            for(int j = 0;j<b.length();j++)\n            {\n                ans += findMaximumSubstr(i,j,0,dp,a,b);\n            }\n        return ans;\n        \n    }\n}\n```
[]