Easy to Understand | Simple | Clean | Crisp Code | Beats 90% | C++ | Java | Python | Kotlin
Problem Statement\n Describe your first thoughts on how to solve this problem. \nGiven 2 strings. Find the longest possible Substring in both of them which can 
# Problem Statement\n<!-- Describe your first thoughts on how to solve this problem. -->\nGiven 2 strings. Find the longest possible Substring in both of them which can be same after applying some operations on String **s** less than **maxCost**.\n\n# Intuition and Approach\n<!-- Describe your approach to solving the problem. -->\nHere, We need to find the **Longest Possible Substring** which is present in both the Strings **s** and **t**. \n\nSo, If we think greedily then we will try to perform all operations which are having the least cost over the complete string in order to **Maximize** the Number of Operations Performed on the String **s**. But, it doesn\'t ensures that the **Resulting string** will be having the **Longest Possible Substring** present in it.\n\nDifference is states as the Difference of ASCII values of Characters at Specific Index\n\nGiven Below Example for Better Understanding\ns = "abcd"\nt = "bdfc"\nmaxCost = 3\n\nTotal Difference At Corresponding Indices are\n```\nfor i in range(0,len(s)):\n    abs( s[i] - t[i] )\n```\nThereFore, \n$$[abs(s[0] - t[0]), abs(s[1] - t[1]), abs(s[2] - t[2]), abs(s[3] - t[3]) ] = [1, 2, 3, 1] $$\n\n##### If Greedily is Considered,\n\nThen, we will First make 1st index equal for both strings with cost 1.\nRemaining Cost = 3 - 1 = 2\nAfter Operation Strings\ns = "bbcd"\nt = "bdfc"\n\nNow, we will make operations at last index equal for both strings with cost 1.\nRemaining Cost = 2 - 1 = 1\nAfter Operation Strings\ns = "bbcc"\nt = "bdfc"\n\nNow, We can not make any further operations on String **s** with Cost = 1.\n\nHere, Total Longest Possible Substring of Equal Length in Strings **s** and **t** are 1.\n\ns = "abcd"\nt = "bdfc"\n\nAfter Applying 2 Continuous Operations from index 1\ns = "bdcd"\nt = "bdfc"\nRemaining Cost = 3 - 1(1st index) - 2(2nd index) = 0\nLongest Possible Substring = 2\n\nIf we Start Performing Operations from index 2 by Skipping index 1\ns = "adcd"\ng = "bdfc"\nRemaining Cost = 3 - 2(2nd index) = 1\nNow further No More Operations can be performed\nLongest Possible Substring = 1\n\nSimilarly, for index 3 and index 4\ns = "abfd"\nt = "bdfc"\nRemaining Cost = 3 - 3(3rd index) = 0\nLongest Possible Substring = 1\n\ns = "abcc"\nt = "bdfc"\nRemaining Cost = 3 - 1(4th index) = 2\nLongest Possible Substring = 1\n\nTherefore, If we apply Operations at indexes 1 and 2, which is equal to the total maxCost = 3, We can obtain a string of length 2, which is **greater than** the Total Longest Possible Substring Obtained from the Greedy Approach.\n\nFrom this we Understand that \n***All Operations that are to be performed on the string **s** should be consecutive.***\n\nIn order to Perform Operation on string **s** consecutively we can use 2 pointers i and j in which we will iterate index j from index i until we get a sum which is greater than to maxCost from index i. We will iterate index i from 0 to n\n***Note - Index i is taken into consideration here***\n```\nwhile ( j < len(s) and sum >= maxCost ):\n    j += 1\n```\n\nAt the arrival of such an index when sum becomes greater than maxCost we can store the difference of indices into result.\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int equalSubstring(string s, string t, int maxCost) {\n        int n = s.size();\n        vector<int> pref(n);\n        for ( int i = 0 ; i < n ; i++ ) {\n            pref[i] = ( i - 1 >= 0 ? pref[i-1] : 0 ) + abs(s[i]-t[i]);\n            // std::cout << pref[i] << " ";\n        }\n        int ans = 0;\n        for ( int i = 0 ; i < n ; i++ ) {\n            int sum = ( i - 1 >= 0 ? pref[i-1] : 0 ) + maxCost;\n            int u = upper_bound(pref.begin(),pref.end(),sum) - pref.begin();\n            ans = std::max({ ans, u-i });\n        }\n        return ans;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int equalSubstring(String s, String t, int maxCost) {\n        int[] pref = new int[s.length()];\n        for ( int i = 0 ; i < s.length() ; i++ ) {\n            pref[i] = Math.abs( ((int)s.charAt(i)) - ((int)t.charAt(i)) );\n            if ( i > 0 ) {\n                pref[i] += pref[i-1];\n            }\n        }\n        int ans = 0, j = 0;\n        for ( int i = 0 ; i < s.length() ; i++ ) {\n            int curr = maxCost;\n            if ( i - 1 >= 0 ) {\n                curr += pref[i-1];\n            }\n            while ( j < s.length() && curr >= pref[j] ) {\n                j++;\n            }\n            ans = Math.max( ans, j - i );\n        }\n        return ans;\n    }\n}\n```\n```Python []\nclass Solution:\n    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n        pref = []\n        for i in range(0,len(s)):\n            pref.append(abs( ord(s[i]) - ord(t[i]) ))\n            if ( len(pref) > 1 ):\n                pref[-1] += pref[-2]\n        ans, j = 0, 0\n        for i in range(0,len(s)):\n            curr = maxCost\n            if ( i - 1 >= 0 ):\n                curr += pref[i-1]\n            while ( j < len(s) and curr >= pref[j] ):\n                j += 1\n            ans = max( ans, j - i )\n        return ans\n```\n```Kotlin []\nimport kotlin.math.abs\nclass Solution {\n    fun equalSubstring(s: String,t: String,maxCost: Int): Int {\n        var ans: Int = 0;\n        var pref = IntArray(s.length);\n        for (item in s.indices) {\n            pref[item] = abs(s[item] - t[item])\n            if ( item > 0 ) {\n                pref[item] += pref[item-1];\n            }\n        }\n        var j:Int = 0\n        for (i in 0..<s.length) {\n            var sum:Int = maxCost;\n            if ( i - 1 >= 0 ) {\n                sum += pref[i-1]\n            }\n            while ( j < s.length && sum >= pref[j] ) {\n                j += 1\n            }\n            ans = max( ans, j - i );\n        }\n        return ans\n    }\n}\n```\n# **Please Upvote.** \n# **If You Liked, Understood the Solution.**\n# Thanks For Reading
['Array', 'Two Pointers', 'String', 'Binary Search', 'Sliding Window', 'Prefix Sum', 'C++', 'Java', 'Python3', 'Kotlin']