Easy to understand solution. Beginner friendly solution. O(n) Time Complexity.
Intuition\n Describe your first thoughts on how to solve this problem. \n1. Cost Calculation: Calculate the cost to transform each character of s to t. This giv
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. **Cost Calculation:** Calculate the cost to transform each character of s to t. This gives us the cost array.\n\n2. **Prefix Sum:** Use the prefix sum array to quickly compute the total cost of any substring.\n\n3. **Binary Search:** Use binary search to efficiently find the maximum length of the substring that can be transformed within the given cost.\n\n4. **Sliding Window Check:** For each potential length found via binary search, use the prefix sum to check if there exists a valid substring of that length.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Calculate the Cost Array:**\nFirst, we calculate the cost array where each element represents the cost of changing s[i] to t[i]\n```\nvector<int> cost(n, 0);\nfor(int i = 0; i < n; i++) {\n    cost[i] = abs(s[i] - t[i]);\n}\n\n```\n2. **Calculate the Prefix Sum Array:**\nNext, we create a prefix sum array to efficiently calculate the sum of costs for any substring.\n```\nvector<int> prefixSum(n + 1, 0);\nfor(int i = 1; i <= n; i++) {\n    prefixSum[i] = prefixSum[i - 1] + cost[i - 1];\n}\n\n```\n3. **Binary Search for the Maximum Length:**\nWe use binary search to find the maximum length of the substring that satisfies the cost condition.  \nThe idea is to check for each possible length mid if there exists a substring of this length whose total transformation cost is within maxCost.\n```\nint left = 0;\nint right = n;\nint ans = 0;\nwhile (left <= right) {\n    int mid = (left + right) / 2;\n    if (check(prefixSum, maxCost, mid)) {\n        ans = mid;\n        left = mid + 1;\n    } else {\n        right = mid - 1;\n    }\n}\n\n```\n4. **Check Function:**\nThe check function verifies if there is any substring of length mid whose transformation cost does not exceed maxCost.\nThis is done by iterating over the prefix sum array and calculating the cost for each possible substring of length mid.\n```\nbool check(vector<int> &prefixSum, int maxCost, int mid) {\n    for (int i = 0; i + mid < prefixSum.size(); i++) {\n        if (prefixSum[i + mid] - prefixSum[i] <= maxCost) {\n            return true;\n        }\n    }\n    return false;\n}\n```\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n# Please upvote my solution, if found helpful. I am literally crying right now.\n\n# Code\n```\nclass Solution {\npublic:\n    int equalSubstring(string s, string t, int maxCost) {\n        int n = s.size();\n        vector<int> cost(n, 0);\n        for(int i = 0; i < n; i++)\n        {\n            cost[i] = abs(s[i] - t[i]);\n        }\n        vector<int> prefixSum(n+1, 0);\n        for(int i = 1; i <= n; i++)\n        {\n            prefixSum[i] = prefixSum[i-1] + cost[i-1];\n        }\n        int left = 0;\n        int right = n;\n        int ans = 0;\n        while(left <= right)\n        {\n            int mid = (left + right) / 2;\n            if(check(prefixSum, maxCost, mid))\n            {\n                ans = mid;\n                left = mid + 1;\n            }\n            else\n            {\n                right = mid - 1;\n            }\n        }\n        return ans;\n    }\n    bool check(vector<int> &prefixSum, int maxCost, int mid)\n    {\n        for(int i = 0; i + mid < prefixSum.size(); i++)\n        {\n            if(prefixSum[i+mid] - prefixSum[i] <= maxCost)\n            {\n                return true;\n            }\n        }\n        return false;\n    }\n};\n```
['Binary Search', 'Recursion', 'Sliding Window', 'Prefix Sum', 'C++']