Java Sliding Window [67 ms] Faster than 100%
The approach is very similar to sliding window with atmost K distinct elements. The only difference here is that I am trying to generate the substring and store
The approach is very similar to sliding window with atmost K distinct elements. The only difference here is that I am trying to generate the substring and store it in a map.\n**EDIT: O(n) solution is mentioned after this solution with explanation**\n```\nclass Solution {\n    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {\n        if(s.length() == 0)\n            return 0;\n        int map[] = new int[128];\n        Map<String, Integer> strMap = new HashMap<>();\n        char[] cs = s.toCharArray();\n        int start = 0, k = maxLetters;\n        int max = 0;\n        for(int i = 0; i < s.length(); i++) {\n            if(map[cs[i]] == 0) {\n                k--;\n            }\n            map[cs[i]] ++;\n            while(start < cs.length && k < 0) {\n                map[cs[start]]--;\n                if(map[cs[start]] == 0)\n                    k++;\n                start++;\n            }\n            int res = i - start + 1;\n            for(int x = minSize; x <= Math.min(res, maxSize); x++) {\n                int index = i-x+1;\n                String subStr = s.substring(index, index + x);\n                strMap.put(subStr, strMap.getOrDefault(subStr, 0) + 1);\n                max = Math.max(max, strMap.get(subStr));\n            }\n        }\n        return max;\n    }\n}\n\n```\nFigured out from other solutions that this can actually be optimised to O(n). The understanding is that we will always work only with the minSize string and not consider the remaining strings and the reason behind this is simply the fact that the chances of a smaller string appearing in the bigger string is equal to or more than once. \nFor example if we have a string ``` abab ``` then the smaller string ```ab``` appears twice in the string ```abab``` so when we are asked to find the maximum occurence of any substring we will always get it from the minimum size string instead of the bigger ones.\n\nHere is the code for the same.\n\n```\n    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {\n        Map<Character, Integer> map = new HashMap<>();\n        Map<String, Integer> res = new HashMap<>();\n        int max = 0;\n        int end = 0, begin = 0;\n        for(end = 0; end < s.length(); end++) {\n            map.put(s.charAt(end), map.getOrDefault(s.charAt(end), 0) + 1);\n            if (end - begin + 1 > minSize) {\n                char c = s.charAt(begin);\n                begin += 1;\n                map.put(c, map.get(c) - 1);\n                if (map.get(c) == 0)\n                    map.remove(c);\n            }\n            if (end - begin + 1 == minSize && map.size() <= maxLetters) {\n                String substr = s.substring(begin, begin+minSize);\n                res.put(substr, res.getOrDefault(substr, 0) + 1);\n                max = Math.max(max, res.get(substr));\n            }\n        }\n        return max;\n    }
[]