💯✅🔥Easy Java Solution|| 12 ms ||≧◠‿◠≦✌
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is about finding the maximum length of a substring in s that is equal to th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is about finding the maximum length of a substring in s that is equal to the corresponding substring in t and the sum of the absolute differences between characters in the two substrings does not exceed maxCost.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe approach is to maintain a prefix sum array prefixDiffSum where prefixDiffSum[i] stores the sum of absolute differences between characters in s and t from the beginning to the i-th character. Then, for each character in s, we perform a binary search to find the maximum length of a substring that ends at the current character and has a sum of absolute differences not exceeding maxCost.\n# Complexity\n- Time complexity:O(n log n), where n is the length of the strings s and t. \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n), where n is the length of the strings s and t\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int equalSubstring(String s, String t, int maxCost) {\n        int[] prefixDiffSum = new int[s.length() + 1];\n        int Max = 0;\n        for (int i = 1; i < s.length() + 1; i++) {\n            prefixDiffSum[i] = prefixDiffSum[i - 1] + Math.abs(s.charAt(i - 1) - t.charAt(i - 1));   // Stores sum of differences from beginning till i\n            int start = 0;\n            int end = i;\n            while (start <= end) {\n                int mid = start + (end - start) / 2;\n                if (prefixDiffSum[i] - prefixDiffSum[mid] <= maxCost) {\n                    Max = Math.max(Max, i - mid);\n                    end = mid - 1;\n                } else {\n                    start = mid + 1;\n                }\n            }\n        }\n        return Max;\n    }\n}\n```\n![upvote.png](https://assets.leetcode.com/users/images/b9855c44-ec4f-4d20-b43c-53d595859710_1716856890.7118201.png)\n
['String', 'Sliding Window', 'String Matching', 'Java']