LeetCode 1297: Maximum Number of Occurrences of a Substring Solution

Master LeetCode problem 1297 (Maximum Number of Occurrences of a Substring), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1297. Maximum Number of Occurrences of a Substring

Medium

Hash Table String Sliding Window

Problem Explanation

Explanation:

To solve this problem, we can use a sliding window approach to iterate through all possible substrings within the given constraints. We will keep track of the frequency of each substring that we encounter and update the maximum occurrences accordingly. Here are the steps:

Initialize a hashmap to store the frequency of substrings within the constraints.
Use a sliding window technique to iterate over all possible substrings.
Update the frequency of each substring and check if it satisfies the conditions.
Keep track of the maximum occurrences of any substring that we encounter.
Return the maximum occurrences as the result.

Time Complexity: O(n) where n is the length of the input string s. Space Complexity: O(n) for the hashmap.

Solution Code

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        Map<String, Integer> map = new HashMap<>();
        int[] count = new int[26];
        int unique = 0;
        int left = 0;
        int maxCount = 0;

        for (int right = 0; right < s.length(); right++) {
            if (count[s.charAt(right) - 'a'] == 0) unique++;
            count[s.charAt(right) - 'a']++;

            if (right - left + 1 > minSize) {
                count[s.charAt(left) - 'a']--;
                if (count[s.charAt(left) - 'a'] == 0) unique--;
                left++;
            }

            if (right - left + 1 >= minSize && right - left + 1 <= maxSize && unique <= maxLetters) {
                String substring = s.substring(left, right + 1);
                map.put(substring, map.getOrDefault(substring, 0) + 1);
                maxCount = Math.max(maxCount, map.get(substring));
            }
        }

        return maxCount;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1297 (Maximum Number of Occurrences of a Substring)?

This page provides optimized solutions for LeetCode problem 1297 (Maximum Number of Occurrences of a Substring) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1297 (Maximum Number of Occurrences of a Substring)?

The time complexity for LeetCode 1297 (Maximum Number of Occurrences of a Substring) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1297 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1297 in Java, C++, or Python.

Back to LeetCode Solutions