Easy PrefSum + BinarySearch O(NLogN)
Intuition\nThe intution came to me when i was solving the question i saw i needed to find a substring sum which leads me to this size or less.\n# Approach\nMade
# Intuition\nThe intution came to me when i was solving the question i saw i needed to find a substring sum which leads me to this size or less.\n# Approach\nMade a prefix sum to calculate sum/change cost in O(1)\nThen i searched substring of size k which satisfy the value and then if it satisfied i searched for higher values otherwise lesser size.\n# Complexity\n- Time complexity:O(NLogN)\n\n- Space complexity:O(N)\n\n# Code\n```\nclass Solution {\npublic:\n    bool check(vector<int>& pref , int cost , int mid){\n        int l = 0 , r = mid;\n        int flag = false;\n        while(r < pref.size()){\n            int sum = pref[r] - pref[l];\n            if(sum <= cost){\n                flag = true;\n                break;\n            }\n            l++;\n            r++;\n        }\n        return flag;\n    }\n    int equalSubstring(string s, string t, int cost) {\n        int n = s.size();\n        vector<int> pref(n + 1 , 0);\n        for(int i = 1 ; i <= n ; i++){\n            pref[i] = pref[i-1] + abs((s[i - 1] - \'a\') - (t[i - 1] - \'a\'));\n        }\n        int l = 0 , h = s.size()+1;\n        int ans = 0;\n        while(l <= h){\n            int mid = l + (h - l)/2;\n            if(check(pref , cost , mid)){\n                ans = mid ;\n                l = mid + 1;\n            }\n            else{\n                h = mid - 1;\n            }\n        }\n        return ans;\n    }\n};\n```
['Binary Search', 'Prefix Sum', 'C++']