✅Detailed Explanation💯Beats 100%🔥Sliding Window (+Optimised)🔥1 & 2 pass solutions🔥O(n), O(1)🔥
\nSubmission Link\n> Don\'t mind leetcode submission rating too much, its very random.\n\n# \uD83C\uDFAF Problem Explanation:\nWe are given two strings s and t 
![image.png](https://assets.leetcode.com/users/images/3f916628-e284-44c4-b621-834f7bea6137_1716857189.9352129.png)\n[Submission Link](https://leetcode.com/problems/get-equal-substrings-within-budget/submissions/1269912694?envType=daily-question&envId=2024-05-28)\n> Don\'t mind leetcode submission rating too much, its very random.\n\n# \uD83C\uDFAF Problem Explanation:\nWe are given two strings `s` and `t` of the same length and a number `maxCost`. The goal is to change `s` to `t` character by character. Changing the `s[i]` to `t[i]` costs the absolute difference between their ASCII values. We need to find the longest substring of `s` that you can change to match `t` without the total cost exceeding `maxCost`. If we can\'t change any substring within the cost, return 0.\n\n## \uD83D\uDD0D Methods To Solve This Problem:\nThis post covers the following approaches:\n1. Sliding Window, 2 pass.\n2. Optimised Sliding Window, 1 pass \uD83D\uDD25.\n\n---\n\n# Method 1: Sliding Window\n\n## \uD83E\uDD14 Intuition:\n- This is classic sliding window question. To solve this problem think of using a sliding window. \n- Imagine you have a window that you slide from right over the strings `s` and `t` to keep track of the cost of changing characters within that window. \n- If the cost exceeds `maxCost`, you shrink the window from the left side until the cost is manageable again. This way, you can efficiently find the longest substring that fits within the allowed cost.\n\n\n\n## \uD83E\uDDE0 Approach:\n1. **Set Up Pointers and Variables**:\n   - Use two pointers, `l` (left) and `r` (right), to represent the current window.\n   - Initialize `cost` to 0 to keep track of the current window\'s conversion cost.\n   - Initialize `result` to 0 to store the maximum length of a valid substring found.\n\n2. **Expand the Window**:\n   - Iterate through the string using the right pointer `r`.\n   - For each character, calculate the cost of changing `s[r]` to `t[r]` and add it to `cost`.\n\n3. **Shrink the Window**:\n   - If `cost` exceeds `maxCost`, move the left pointer `l` to the right to reduce the window size. Subtract the cost of changing `s[l]` to `t[l]` from `cost`.\n\n4. **Update the Result**:\n   - After adjusting the window, update `result` with the maximum length of the current valid window.\n\n5. **Return the Result**:\n   - Finally, return the maximum length of the substring that can be changed within the given cost constraint.\n\n## \u2699\uFE0F Dry Run:\n##### Input: s = "abcd", t = "bcdf", maxCost = 3\n| Iteration |   Window  |  l  |  r  |       Sliding Window       | abs(s[r] - t[r]) |  cost  |         result          |\n|:---------:|:---------:|:---:|:---:|:--------------------------:|:----------------:|:------:|:-----------------------:|\n|     1     | Expanding |  0  |  0  | "***a***bcd"  "***b***cdf" |     1 (\'a\'-\'b\')  |   1    | `max(0, 0 - 0 + 1)` = 1 |\n|     2     | Expanding |  0  |  1  | "***ab***cd"  "***bc***df" |     1 (\'b\'-\'c\')  |   2    | `max(1, 1 - 0 + 1)` = 2 |\n|     3     | Expanding |  0  |  2  | "***abc***d"  "***bcd***f" |     1 (\'c\'-\'d\')  |   3    | `max(2, 2 - 0 + 1)` = 3 |\n|     4     | Expanding |  0  |  3  | "***abcd***"  "***bcdf***" |     2 (\'d\'-\'f\')  |   5    |   Cost exceeds maxCost  |\n|     4     | Shrinking |  1  |  3  | "a***bcd***"  "b***cdf***" |    -1 (\'a\'-\'b\')  |   4    |   Cost exceeds maxCost  |\n|     4     | Shrinking |  2  |  3  | "ab***cd***"  "bc***df***" |    -1 (\'b\'-\'c\')  |   3    | `max(3, 3 - 2 + 1)` = 3 |\n##### Output: result = 3\n\n\n## \uD83D\uDCD2 Complexity:\n- \u23F0 Time complexity: $$O(n)$$. Each character in the string is processed at most twice, once by the right pointer and once by the left pointer. Thus 2 pass solution.\n- \uD83E\uDDFA Space complexity: $$O(1)$$. No additional 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        l, cost = 0, 0\n        result = 0\n\n        for r in range(len(s)):\n            cost += abs(ord(s[r]) - ord(t[r]))\n\n            while cost > maxCost:\n                cost -= abs(ord(s[l]) - ord(t[l]))\n                l += 1\n\n            result = max(result, r - l + 1)\n        \n        return result\n```\n``` java []\nclass Solution {\n    public int equalSubstring(String s, String t, int maxCost) {\n        int l = 0, cost = 0, result = 0;\n\n        for (int r = 0; r < s.length(); r++) {\n            cost += Math.abs(s.charAt(r) - t.charAt(r));\n\n            while (cost > maxCost) {\n                cost -= Math.abs(s.charAt(l) - t.charAt(l));\n                l++;\n            }\n\n            result = Math.max(result, r - l + 1);\n        }\n\n        return result;\n    }\n}\n```\n``` cpp []\nclass Solution {\npublic:\n    int equalSubstring(string s, string t, int maxCost) {\n        int l = 0, cost = 0, result = 0;\n\n        for (int r = 0; r < s.length(); r++) {\n            cost += abs(s[r] - t[r]);\n\n            while (cost > maxCost) {\n                cost -= abs(s[l] - t[l]);\n                l++;\n            }\n\n            result = max(result, r - l + 1);\n        }\n\n        return result;\n    }\n};\n```\n``` javascript []\nvar equalSubstring = function(s, t, maxCost) {\n    let l = 0, cost = 0, result = 0;\n\n    for (let r = 0; r < s.length; r++) {\n        cost += Math.abs(s.charCodeAt(r) - t.charCodeAt(r));\n\n        while (cost > maxCost) {\n            cost -= Math.abs(s.charCodeAt(l) - t.charCodeAt(l));\n            l++;\n        }\n\n        result = Math.max(result, r - l + 1);\n    }\n\n    return result;\n};\n```\n\n---\n\n\n# Method 2: Optimised Sliding Window [1 Pass]\uD83D\uDD25BEST\uD83D\uDD25\n\n## \uD83E\uDD14 Intuition:\nIn the above approach we were making a note of `result`. Do we really have to do that?\nWe only need max length. We can expand sliding window as before and when we have to shrinking window, lets just shrinking it by 1 `l++` maintaining max length. `l` will incremented for each `r` increment when `cost` is not satisfied, in case `cost` is satisfied `r` is incremented and l remains stationary, increasing window length.\n\n## \uD83E\uDDE0 Approach:\n1. **Set Up Pointers and Variables**:\n   - Use two pointers, `l` (left) and `r` (right), to represent the current window.\n   - Instead of initializing `cost` and `result`, we directly update `maxCost` as we iterate through the string.\n\n2. **Expand and Shrink the Window**:\n   - Iterate through the string using the right pointer `r`.\n   - For each character, subtract the cost of changing `s[r]` to `t[r]` from `maxCost`.\n   - If `maxCost` becomes negative, indicating that the current window exceeds the cost constraint, move the left pointer `l` to the right to shrink the window. Add the cost of changing `s[l]` to `t[l]` back to `maxCost`.\n\n3. **Update the Result**:\n   - Keep track of the maximum length of the valid window (`r - l + 1`).\n\n4. **Return the Result**:\n   - Finally, return the maximum length of the substring that can be changed within the given cost constraint.\n\n\n\n## \u2699\uFE0F Dry Run:\n##### Inputs: s = "abcd", t = "bcdf", maxCost = 3\n| Iteration |  Window   |   l   |   r   |        Sliding Window         | abs(s[r] - t[r]) |  maxCost  |    r - l    |\n|:---------:|:---------:|:-----:|:-----:|:-----------------------------:|:----------------:|:---------:|:-----------:|\n|     1     | Expanding |   0   |   0   |  "***a***bcd"  "***b***cdf"   |     1 (\'a\'-\'b\')  |     2     |      1      |\n|     2     | Expanding |   0   |   1   |  "***ab***cd"  "***bc***df"   |     1 (\'b\'-\'c\')  |     1     |      2      |\n|     3     | Expanding |   0   |   2   |  "***abc***d"  "***bcd***f"   |     1 (\'c\'-\'d\')  |     0     |      3      |\n|     4     | Expanding |   0   |   3   |  "***abcd***"  "***bcdf***"   |     2 (\'d\'-\'f\')  |    -2     | Cost exceeds maxCost |\n|     4     | Shrinking |   1   |   3   |  "a***bcd***"  "b***cdf***"   |    -1 (\'a\'-\'b\')  |    -1     | Cost exceeds maxCost |\n##### Output: result = 3\n\n\n## \uD83D\uDCD2 Complexity:\n- \u23F0 Time complexity: $$O(n)$$. Each character in the string is processed at most once, once by the right pointer and left pointer is constant. Thus 1 pass solution.\n- \uD83E\uDDFA Space complexity: $$O(1)$$. No additional 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        l = 0\n        for r in range(len(s)):\n            maxCost -= abs(ord(s[r]) - ord(t[r]))\n            if maxCost < 0:\n                maxCost += abs(ord(s[l]) - ord(t[l]))\n                l += 1\n\n        return r - l + 1\n```\n``` java []\nclass Solution {\n    public int equalSubstring(String s, String t, int maxCost) {\n        int l = 0, r;\n        for (r = 0; r < s.length(); r++) {\n            maxCost -= Math.abs(s.charAt(r) - t.charAt(r));\n            if (maxCost < 0)\n                maxCost += Math.abs(s.charAt(l) - t.charAt(l++));\n        }\n        return r - l;\n    }\n}\n```\n``` cpp []\nclass Solution {\npublic:\n    int equalSubstring(string s, string t, int maxCost) {\n        int l = 0, r;\n        for (r = 0; r < s.length(); r++) {\n            maxCost -= abs(s[r] - t[r]);\n            if (maxCost < 0)\n                maxCost += abs(s[l] - t[l++]);\n        }\n        return r - l;\n    }\n};\n```\n``` javascript []\nvar equalSubstring = function(s, t, maxCost) {\n    let l = 0, r;\n    for (r = 0; r < s.length; r++) {\n        maxCost -= Math.abs(s.charCodeAt(r) - t.charCodeAt(r));\n        if (maxCost < 0)\n            maxCost += Math.abs(s.charCodeAt(l) - t.charCodeAt(l++));\n    }\n    return r - l;\n};\n```\n\n---\n# Please consider giving an Upvote!\n![upvote.png](https://assets.leetcode.com/users/images/5fbeecf2-18f6-4dce-a4a0-f11c859e46ad_1714711173.2665718.png)
['String', 'Sliding Window', 'Prefix Sum', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']