✅Detailed Explanation🔥2 Approaches🔥🔥Extremely Simple and effective🔥🔥🔥 Beginner-friendly🔥
\uD83C\uDFAFProblem Explanation:\nYou are given two strings s and t and integer maxCost. You want to return maximum length of substring from s such that you nee
# \uD83C\uDFAFProblem Explanation:\nYou are given two strings ```s``` and ```t``` and integer ```maxCost```. You want to return maximum length of substring from ```s``` such that you need up to ```maxCost``` cost to change it.\n- "cost" is absolute ASCII difference between s[i] and t[i]\n- Substring is a contiguous sequence of characters within a string\n\n# \uD83D\uDCE5Input:\n- String ```s``` which we have initally\n- String ```t``` to which we want to transform ```s```\n- Integer ```maxCost``` which represents maximum cost of changing substring\n\n# \uD83D\uDCE4Output:\nThe maximum possible length of substring we can change for ```cost <= maxCost```\n\n# \uD83E\uDDE0 Approach 1: Sliding Window \n\n# \uD83E\uDD14 Intuition\nI don\'t know why but it seems to me that in case of that problem to come up with optimized solution is much easier than to come up with relatively slow one.\n- First key point you want to understand that, in fact, we just not interested in strings ```s``` and ```t``` at all. We can compute some array like ```delta``` and just forget about those strings because what we really are interested in is just differences between ```s[i]``` and ```t[i]``` for every ```i```.\n- So, it really comes down to finding the largest sublist of elements in the list such that the sum of the elements does not exceed ```maxCost```, which is actually the very standard sliding window problem.\n- Let\'s move on to the code, and then to a more complex, but less effective solution.\n\n# \uD83D\uDCBB Coding \nAs was said earlier we will use Sliding window approach for this problem\n- Initialize ```res``` variable which will contain maximum length of substring we\'ve found, ```cur_start``` variable which store current start of substring (since our sliding window will have dynamic size) and ```cur_cost``` variable which just store the cost of current substring\n- We want to iterate through every ```last_ind``` and apply this operations on every step:\n    - Add new element to the sliding window\n    - While our ```cur_cost``` is greater than ```maxCost``` move left pointer to the right so decreasing the size of the window and total cost of the substring.\n    - If length of current valid window is greater than maximum length we\'ve seen so far update it \n- Return result which is stored in ```res```\n\n# \uD83D\uDCD2 Complexity\n- \u23F0 Time complexity: O(n), every element in array will be called at most twice so this is O(2n) => O(n)\n- \uD83E\uDDFA Space complexity: O(1), since no extra space is used\n\n# \uD83E\uDDD1\u200D\uD83D\uDCBB Code\n``` python []\nclass Solution:\n    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n        res: int = 0\n        cur_cost: int = 0\n        cur_start: int = 0\n\n        for last_ind in range(len(s)):\n            cur_cost += abs(ord(s[last_ind]) - ord(t[last_ind]))\n\n            while cur_cost > maxCost:\n                cur_cost -= abs(ord(s[cur_start]) - ord(t[cur_start]))\n                cur_start += 1\n\n            if last_ind - cur_start + 1 > res:\n                res = last_ind - cur_start + 1\n\n        return res\n```\n``` C++ []\nclass Solution {\npublic:\n    int equalSubstring(string s, string t, int maxCost) {\n        int res = 0;\n        int cur_cost = 0;\n        int cur_start = 0;\n\n        for (int last_ind = 0; last_ind < s.size(); last_ind++) {\n            cur_cost += abs(s[last_ind] - t[last_ind]);\n\n            while (cur_cost > maxCost) {\n                cur_cost -= abs(s[cur_start] - t[cur_start]);\n                cur_start++;\n            }\n\n            if (last_ind - cur_start + 1 > res) {\n                res = last_ind - cur_start + 1;\n            }\n        }\n\n        return res;\n    }\n};\n```\n``` JavaScript []\nvar equalSubstring = function(s, t, maxCost) {\n    let res = 0;\n    let cur_cost = 0;\n    let cur_start = 0;\n\n    for (let last_ind = 0; last_ind < s.length; last_ind++) {\n        cur_cost += Math.abs(s.charCodeAt(last_ind) - t.charCodeAt(last_ind));\n\n        while (cur_cost > maxCost) {\n            cur_cost -= Math.abs(s.charCodeAt(cur_start) - t.charCodeAt(cur_start));\n            cur_start++;\n        }\n\n        if (last_ind - cur_start + 1 > res) {\n            res = last_ind - cur_start + 1;\n        }\n    }\n\n    return res;\n};\n```\n``` Java []\nclass Solution {\n    public int equalSubstring(String s, String t, int maxCost) {\n        int res = 0;\n        int cur_cost = 0;\n        int cur_start = 0;\n\n        for (int last_ind = 0; last_ind < s.length(); last_ind++) {\n            cur_cost += Math.abs(s.charAt(last_ind) - t.charAt(last_ind));\n\n            while (cur_cost > maxCost) {\n                cur_cost -= Math.abs(s.charAt(cur_start) - t.charAt(cur_start));\n                cur_start++;\n            }\n\n            if (last_ind - cur_start + 1 > res) {\n                res = last_ind - cur_start + 1;\n            }\n        }\n\n        return res;\n    }\n}\n```\n``` C []\nint equalSubstring(char* s, char* t, int maxCost) {\n    int res = 0;\n    int cur_cost = 0;\n    int cur_start = 0;\n\n    for (int last_ind = 0; last_ind < strlen(s); last_ind++) {\n        cur_cost += abs(s[last_ind] - t[last_ind]);\n\n        while (cur_cost > maxCost) {\n            cur_cost -= abs(s[cur_start] - t[cur_start]);\n            cur_start++;\n        }\n\n        if (last_ind - cur_start + 1 > res) {\n            res = last_ind - cur_start + 1;\n        }\n    }\n\n    return res;\n}\n```\n\n\n# \uD83E\uDDE0 Approach 2: Prefix sum and binary search\n\n# \uD83E\uDD14 Intuition\nThis approach is quite harder to come up with or implement but it\'s big advantage to know different approaches to the same problem.\n- Unlike the previous solution, this time let\u2019s actually define an array that will store the cost to change one letter to another, but at the same time we want to store not just one cost, but a prefix sum in order to effectively find the cost of the current substring.\n- We will iterate through every possible ```right_index``` and call binary search on ```costs[right_index] - maxCost``` in order to find the most left index where we can put our pointer left so that s[left:right] has cost less than or equal to maxCost\n\n# \uD83D\uDCBB Coding \n- Initialize preffix sum array ```costs``` and calculate it with loop\n- Write ```binary_search``` function which will return not whether element exist in array but the left most index from where we can start to fit ```maxCost``` (so we need to return mid + 1, because index mid will contain index to where we can put this new sum and so value which is actually is our substring will be 1 index right)\n- Iterate through every possible ```right``` index and call binary search to find most left index, calculate new length and update result\n### [Here\'s vizualization on example](https://pythontutor.com/render.html#code=class%20Solution%3A%0A%20%20%20%20def%20equalSubstring%28self,%20s%3A%20str,%20t%3A%20str,%20maxCost%3A%20int%29%20-%3E%20int%3A%0A%20%20%20%20%20%20%20%20costs%3A%20list%5Bint%5D%20%3D%20%5B0%20for%20_%20in%20range%28len%28s%29%20%2B%201%29%5D%0A%20%20%20%20%20%20%20%20for%20ind%20in%20range%281,%20len%28s%29%20%2B%201%29%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20costs%5Bind%5D%20%3D%20costs%5Bind%20-%201%5D%20%2B%20abs%28ord%28s%5Bind%20-%201%5D%29%20-%20ord%28t%5Bind%20-%201%5D%29%29%0A%0A%20%20%20%20%20%20%20%20res%3A%20int%20%3D%200%0A%0A%20%20%20%20%20%20%20%20for%20right_index%20in%20range%281,%20len%28costs%29%29%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20min_left%3A%20int%20%3D%20self.binary_search%28costs,%20costs%5Bright_index%5D%20-%20maxCost%29%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20right_index%20-%20min_left%20%3E%20res%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20right_index%20-%20min_left%0A%0A%20%20%20%20%20%20%20%20return%20res%0A%0A%20%20%20%20def%20binary_search%28self,%20arr,%20x%29%20-%3E%20int%3A%0A%20%20%20%20%20%20%20%20lo%3A%20int%20%3D%200%0A%20%20%20%20%20%20%20%20hi%3A%20int%20%3D%20len%28arr%29%20-%201%0A%20%20%20%20%20%20%20%20while%20lo%20%3C%20hi%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20mid%3A%20int%20%3D%20%28lo%20%2B%20hi%29%20//%202%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20arr%5Bmid%5D%20%3C%20x%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20lo%20%3D%20mid%20%2B%201%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20hi%20%3D%20mid%0A%20%20%20%20%20%20%20%20return%20lo%0A%0As%20%3D%20Solution%28%29%0As.equalSubstring%28%22abcd%22,%20%22bcdf%22,%203%29&cumulative=false&curInstr=109&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false) how this works, you can check it if you want.\n\n\n# \uD83D\uDCD2 Complexity\n- \u23F0 Time complexity: O(n logn), we call binary search for every character in s which is O(n) * O(logn) = O(n logn)\n- \uD83E\uDDFA Space complexity: O(n) since we creating array ```costs``` of size n\n\n# \uD83E\uDDD1\u200D\uD83D\uDCBB Code\n``` python []\nclass Solution:\n    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n        costs: list[int] = [0 for _ in range(len(s) + 1)]\n        for ind in range(1, len(s) + 1):\n            costs[ind] = costs[ind - 1] + abs(ord(s[ind - 1]) - ord(t[ind - 1]))\n\n        res: int = 0\n\n        for right_index in range(1, len(costs)):\n            min_left: int = self.binary_search(costs, costs[right_index] - maxCost)\n            if right_index - min_left > res:\n                res = right_index - min_left\n\n        return res\n\n    def binary_search(self, arr, x) -> int:\n        lo: int = 0\n        hi: int = len(arr) - 1\n        while lo < hi:\n            mid: int = (lo + hi) // 2\n            if arr[mid] < x:\n                lo = mid + 1\n            else:\n                hi = mid\n        return lo\n```\n``` C++ []\nclass Solution {\npublic:\n    int binary_search(const vector<int>& arr, int x) {\n        int lo = 0;\n        int hi = arr.size() - 1;\n        while (lo < hi) {\n            int mid = (lo + hi) / 2;\n            if (arr[mid] < x) {\n                lo = mid + 1;\n            } else {\n                hi = mid;\n            }\n        }\n        return lo;\n    }\n\n    int equalSubstring(string s, string t, int maxCost) {\n        int len = s.size();\n        vector<int> costs(len + 1, 0);\n        for (int ind = 1; ind <= len; ind++) {\n            costs[ind] = costs[ind - 1] + abs(s[ind - 1] - t[ind - 1]);\n        }\n\n        int res = 0;\n\n        for (int right_index = 1; right_index <= len; right_index++) {\n            int min_left = binary_search(costs, costs[right_index] - maxCost);\n            if (right_index - min_left > res) {\n                res = right_index - min_left;\n            }\n        }\n\n        return res;\n    }\n};\n```\n``` JavaScript []\nvar binarySearch = function(arr, x) {\n    let lo = 0;\n    let hi = arr.length - 1;\n    while (lo < hi) {\n        let mid = Math.floor((lo + hi) / 2);\n        if (arr[mid] < x) {\n            lo = mid + 1;\n        } else {\n            hi = mid;\n        }\n    }\n    return lo;\n};\n\nvar equalSubstring = function(s, t, maxCost) {\n    let len = s.length;\n    let costs = new Array(len + 1).fill(0);\n    for (let ind = 1; ind <= len; ind++) {\n        costs[ind] = costs[ind - 1] + Math.abs(s.charCodeAt(ind - 1) - t.charCodeAt(ind - 1));\n    }\n\n    let res = 0;\n\n    for (let right_index = 1; right_index <= len; right_index++) {\n        let min_left = binarySearch(costs, costs[right_index] - maxCost);\n        if (right_index - min_left > res) {\n            res = right_index - min_left;\n        }\n    }\n\n    return res;\n};\n```\n``` Java []\nclass Solution {\n    private int binarySearch(int[] arr, int x) {\n        int lo = 0;\n        int hi = arr.length - 1;\n        while (lo < hi) {\n            int mid = (lo + hi) / 2;\n            if (arr[mid] < x) {\n                lo = mid + 1;\n            } else {\n                hi = mid;\n            }\n        }\n        return lo;\n    }\n\n    public int equalSubstring(String s, String t, int maxCost) {\n        int len = s.length();\n        int[] costs = new int[len + 1];\n        costs[0] = 0;\n        for (int ind = 1; ind <= len; ind++) {\n            costs[ind] = costs[ind - 1] + Math.abs(s.charAt(ind - 1) - t.charAt(ind - 1));\n        }\n\n        int res = 0;\n\n        for (int right_index = 1; right_index <= len; right_index++) {\n            int min_left = binarySearch(costs, costs[right_index] - maxCost);\n            if (right_index - min_left > res) {\n                res = right_index - min_left;\n            }\n        }\n\n        return res;\n    }\n}\n```\n``` C []\nint binary_search(int* arr, int len, int x) {\n    int lo = 0;\n    int hi = len - 1;\n    while (lo < hi) {\n        int mid = (lo + hi) / 2;\n        if (arr[mid] < x) {\n            lo = mid + 1;\n        } else {\n            hi = mid;\n        }\n    }\n    return lo;\n}\n\nint equalSubstring(char* s, char* t, int maxCost) {\n    int len = strlen(s);\n    int* costs = (int*)malloc((len + 1) * sizeof(int));\n    costs[0] = 0;\n    for (int ind = 1; ind <= len; ind++) {\n        costs[ind] = costs[ind - 1] + abs(s[ind - 1] - t[ind - 1]);\n    }\n\n    int res = 0;\n\n    for (int right_index = 1; right_index <= len; right_index++) {\n        int min_left = binary_search(costs, len + 1, costs[right_index] - maxCost);\n        if (right_index - min_left > res) {\n            res = right_index - min_left;\n        }\n    }\n\n    free(costs);\n    return res;\n}\n```\n\n## \uD83D\uDCA1I encourage you to check out [my profile](https://leetcode.com/heir-of-god/) and [Project-S](https://github.com/Heir-of-God/Project-S) project for detailed explanations and code for different problems (not only Leetcode). Happy coding and learning! \uD83D\uDCDA\n\n### Please consider *upvote* because I try really hard not just to put here my code and rewrite testcase to show that it works but explain you WHY it works and HOW. Thank you\u2764\uFE0F\n\n## If you have any doubts or questions feel free to ask them in comments. I will be glad to help you with understanding\u2764\uFE0F\u2764\uFE0F\u2764\uFE0F\n\n![There is image for upvote](https://assets.leetcode.com/users/images/5fbeecf2-18f6-4dce-a4a0-f11c859e46ad_1714711173.2665718.png)\n
['String', 'Binary Search', 'C', 'Sliding Window', 'Prefix Sum', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']