1423. Maximum Number Of Occurrences Of A Substring¶

Difficulty: Medium

1423. Maximum Number of Occurrences of a Substring

Medium

Given a string s, return the maximum number of occurrences of any substring under the following rules:

The number of unique characters in the substring must be less than or equal to maxLetters.
The substring size must be between minSize and maxSize inclusive.

Example 1:

Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 occurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).

Example 2:

Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring "aaa" occur 2 times in the string. It can overlap.

Constraints:

1 <= s.length <= 10⁵
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s consists of only lowercase English letters.

Solution¶

class Solution {
    private HashMap<String, Integer> map;
    private int maxi;
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        int n = s.length();
        map = new HashMap<>(); maxi = 0;
        for (int i = minSize; i <= maxSize; i++) getSubstringsOfLengthK(s, i, maxLetters);
        return maxi;
    }
    private ArrayList<String> getSubstringsOfLengthK(String s, int k, int maxLetters) {
        int n = s.length();
        ArrayList<String> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i + k <= n) {
                String current = s.substring(i, i + k);
                HashSet<Character> set = new HashSet<>();
                for (int j = 0; j < current.length(); j++) set.add(current.charAt(j));
                if (set.size() <= maxLetters) map.put(current, map.getOrDefault(current, 0) + 1);
                maxi = Math.max(maxi, map.getOrDefault(current, 0));
            }
        }
        return res;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here