Template for sliding window problems
Inspired by the top post, I create my own template for sliding window problems. I feel it is more generic and is good for all the sliding window problems I stud
Inspired by the top post, I create my own template for sliding window problems. I feel it is more generic and is good for all the sliding window problems I studied so far.\n\n**The template**\n```\nwhile(r<n) {\n\t//process r\n\twhile(r cannot move) {\n\t\t//process l to free r\n\t\tl++;\n\t}\n\t//process r\n\tr++;\n}\n```\n[**3. Longest Substring Without Repeating Characters**](https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/950438/Sliding-window-template)\n```\n\tpublic int lengthOfLongestSubstring(String s) {\n        int l=0, r=0, max = 0;\n        boolean[] window = new boolean[256];\n        while(r<s.length()) {\n            char c = s.charAt(r);\n            while(window[c]) {\n                max = Math.max(max, r-l);\n                window[s.charAt(l)]=false;\n                l++;    \n            }\n            window[c] = true;\n            r++;\n        }\n        return Math.max(max,r-l);\n    }\n```\n**76. Minimum Window Substring**\n```\n\tpublic String minWindow(String s, String t) {\n        int l=0, r=0, tn=t.length(), sn=s.length(), start=0, len=sn+1;\n        int[] count=new int[256];\n        for(int i=0;i<tn;i++) \n            count[t.charAt(i)]++;  \n        while(r<sn) {\n            if(count[s.charAt(r)]-->0) tn--;\n            while(tn==0) { //count[] all neg or 0, r at last element in window\n                if(count[s.charAt(l)]++==0) {\n                    tn=1;\n                    if(r-l+1<len) { //l at 1st element in window\n                        start=l;\n                        len=r-l+1;\n                    }\n                }\n                l++;  \n            }\n            r++;\n        }\n        return len==sn+1?"":s.substring(start,start+len);\n    }\n```\n**159. Longest Substring with At Most Two Distinct Characters**\n```\n\tpublic int lengthOfLongestSubstringTwoDistinct(String s) {\n        int l=0, r=0, types=0, len=0;\n        int[] count = new int[256];\n        while(r<s.length()) {\n            if(count[s.charAt(r)]++==0) {\n                types++;    \n            }\n            while(types==3) {\n                len = Math.max(len, r-l);\n                if(count[s.charAt(l)]--==1) {\n                    types--;\n                }\n                l++;\n            }\n            r++;\n        }\n        return Math.max(len, r-l);\n    }\n```\n **[209. Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/discuss/59141/Evolve-from-brute-force-to-optimal)**\n```\n\tpublic int minSubArrayLen(int s, int[] nums) {\n        int l=0,r=0,n=nums.length,res=n+1,sum=0;\n        while(r<n) {\n            sum+=nums[r];\n            while(sum>=s) {\n                res=Math.min(res,r-l+1); //can be here or outside depdending on the context  \n                sum-=nums[l];\n                l++;\n            }\n            r++;\n        }\n        return res==n+1?0:res;\n    }\n```\n**340. Longest Substring with At Most K Distinct Characters**\n```\n\tpublic int lengthOfLongestSubstringKDistinct(String s, int k) {\n        int l=0, r=0, types=0, len=0;\n        int[] count = new int[256];\n        while(r<s.length()) {\n            if(count[s.charAt(r)]++==0) {\n                types++;    \n            }\n            while(types==k+1) {\n                len = Math.max(len, r-l);\n                if(count[s.charAt(l)]--==1) {\n                    types--;\n                }\n                l++;\n            }\n            r++;\n        }\n        return Math.max(len, r-l);\n    }\n```\n**[904. Fruit Into Baskets](https://leetcode.com/problems/fruit-into-baskets/discuss/1000442/Sliding-window-template)**\n```\n\tpublic int totalFruit(int[] tree) {\n        int l=0, r=0, n = tree.length, types=0, len=0;\n        int[] count = new int[n];\n        while(r<n) {\n            if(count[tree[r]]++==0) {\n                types++;    \n            }\n            while(types==3) {\n                len = Math.max(len, r-l);\n                if(count[tree[l]]--==1) {\n                    types--;\n                }\n                l++;\n            }\n            r++;\n        }\n        return Math.max(len, r-l);\n    }\n```\n**[1004. Max Consecutive Ones III](https://leetcode.com/problems/max-consecutive-ones-iii/discuss/929117/Evolve-from-brute-force-to-optimal)**\n```\n\tpublic int longestOnes(int[] A, int K) {\n        int l=0,r=0,sum=0,max=-1;\n        while(r<A.length) {\n            sum+=A[r];\n            while(sum+K<r-l+1) {\n                max=Math.max(max,r-l);\n                sum-=A[l];\n                l++;\n            }\n            r++;\n        }\n        return Math.max(max,r-l);\n    }\n```\n[**1610. Maximum Number of Visible Points**](https://leetcode.com/problems/maximum-number-of-visible-points/discuss/926504/Template-for-sliding-window-problems)\n```\n\tpublic int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {\n        List<Double> arcs=new ArrayList<>();\n        int ovlp=0;\n        for(List<Integer> point:points) {\n            int dx=point.get(0)-location.get(0), dy=point.get(1)-location.get(1);\n            if(dx==0&&dy==0) ovlp++;\n            else arcs.add(Math.atan2(dx,dy));\n        }\n        Collections.sort(arcs);\n        int n=arcs.size();\n        for(int i=0;i<n;i++)\n            arcs.add(arcs.get(i)+2*Math.PI);\n        double arc=Math.PI*angle/180;\n        int l=0, r=0, max=0;\n        while(r<n*2) {\n            while(arcs.get(r)-arcs.get(l)>arc) {\n                max=Math.max(r-l,max);\n                l++;    \n            }\n            r++;\n        }\n        return max+ovlp;\n    }\n```\n\n
[]