✅ ⬆️ Sliding Window | Prefix Sum | Binary Search 🔥🔥  [Java]
Binary Search\nTC: O(nlogn)\nSC: O(n)\n\npublic int equalSubstring(String s, String t, int maxCost) {\n           int[] costs = new int[s.length() + 1]; // to i
**Binary Search**\nTC: O(nlogn)\nSC: O(n)\n```\npublic int equalSubstring(String s, String t, int maxCost) {\n           int[] costs = new int[s.length() + 1]; // to include 0\n           for (int i = 1; i <= s.length(); ++i) {\n               costs[i] = Math.abs(s.charAt(i - 1) - t.charAt(i - 1));\n           }\n\n           int res = 0;\n\n           for (int i = 1; i < costs.length; ++i) {\n\n               costs[i] += costs[i - 1];\n               int j = Arrays.binarySearch(costs, costs[i] - maxCost);\n               if (j < 0) {\n                   j = -j - 1;\n               }\n               res = Math.max(res, i - j);\n           }\n\n           return res;\n    }\n```\n\n**Sliding Window**\nTC: O(n)\nSC: O(1)\n```\nclass Solution {\n    public int equalSubstring(String s, String t, int maxCost) {\n        int N = s.length();\n        \n        int maxLen = 0;\n        // Starting index of the current substring\n        int start = 0;\n        // Cost of converting the current substring in s to t\n        int currCost = 0;\n        \n        for (int i = 0; i < N; i++) {\n            // Add the current index to the substring\n            currCost += Math.abs(s.charAt(i) - t.charAt(i));\n            \n            // Remove the indices from the left end till the cost becomes less than allowed\n            while (currCost > maxCost) {\n                currCost -= Math.abs(s.charAt(start) - t.charAt(start));\n                start++;\n            }\n            \n            maxLen = Math.max(maxLen, i - start + 1);\n        }\n        \n        return maxLen;\n    }\n}\n```\n\n![image](https://assets.leetcode.com/users/images/d8e70522-744d-42f0-b3a9-82c4c3d9665c_1708866963.8842509.png)\n\n**Please Upvote**
['Binary Tree', 'Prefix Sum', 'Java']