Sliding window vs Prefix sum+Binary search||0ms beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nUse sliding window; it\'s a linear solution with O(1) space.\n\n2nd approach uses prefi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse sliding window; it\'s a linear solution with O(1) space.\n\n2nd approach uses prefix sum. Note that `cost[l...r]=sum[r+1]-sum[l]` where `sum` is 1-indexed prefix sums.\n\n3rd approach is a revision for the 2nd one, within the inner loop uses binary search to move l instead of moving l 1 by 1.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. set the 2 pointers `l=0,r=0`  & `cost=0, len=0`\n2. Find the longest initial valid window by moving `r` while `cost<=maxCost`\n3. When `r==n && cost<=maxCost` return `n`\n4. Initialize `len=r`\n5. Use a nested loop to slide window; `cost+=abs(s[r]-t[r])`\n- in the inner loop proceed to find the next valid window\n```\n while (cost>maxCost) {\n    cost-=abs(s[l]-t[l]);\n    l++;//moving l   \n```\n- update  `len=max(len, r-l+1)`\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\nprefix sum: $O(n)$\n# Code||C++ 0ms beats 100%\n```\nclass Solution {\npublic:\n    static int equalSubstring(string& s, string& t, int maxCost) {\n        const int n=s.size();\n        int l=0, r;// 2 pointers\n        int cost=0, len=0;\n\n        // Initialize the window by moving r while cost<=maxCost\n        for (r = 0; r < n; r++) {\n            cost+=abs(s[r]-t[r]);\n            if (cost>maxCost) {\n                cost-=abs(s[r]-t[r]);\n                break;\n            }\n        }\n\n        // If the initial window exceeds the whole string\n        if (r==n && cost<=maxCost) return n;\n        \n        len=r; //initial length for the valid window\n\n        // Sliding the window\n        for (; r<n; r++) {\n            cost+=abs(s[r]-t[r]);\n            while (cost > maxCost) {\n                cost-=abs(s[l]-t[l]);\n                l++;\n            }\n            len=max(len, r-l+1);\n        }\n        return len;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# C++ prefix sum||0ms beats 100%\n```\nclass Solution {\npublic:\n    static int equalSubstring(string& s, string& t, int maxCost) {\n        const int n=s.size();\n        vector<int> sum(n+1, 0);// 1-indexed prefix sum\n        for(int i=0; i<n; i++)\n            sum[i+1]=sum[i]+abs(s[i]-t[i]);\n        \n        int l=0, r, len=0;\n        for(r=0; r<n; r++){\n            int cost=sum[r+1]-sum[l];\n            while (cost> maxCost) {\n                cost=sum[r+1]-sum[++l];\n            }\n            len=max(len, r-l+1);\n        }\n        return len;\n    }\n};\n\n\n```\n# 3rd C++ using Prefix sum + binary search\n```\nclass Solution {\npublic:\n    static int equalSubstring(string& s, string& t, int maxCost) {\n        const int n=s.size();\n        vector<int> sum(n+1, 0);// 1-indexed prefix sum\n        for(int i=0; i<n; i++)\n            sum[i+1]=sum[i]+abs(s[i]-t[i]);\n        \n        int l=0, r, len=0;\n        for(r=0; r<n; r++){\n            int cost=sum[r+1]-sum[l];\n            if (cost> maxCost) {\n                //Use binary search to move l\n                l=lower_bound(sum.begin()+(l+1), sum.end(), cost-maxCost)-sum.begin();\n                cost=sum[r+1]-sum[l];\n            }\n            len=max(len, r-l+1);\n        }\n        return len;\n    }\n};\n\n```
['Binary Search', 'Sliding Window', 'Prefix Sum', 'C++']