Maximum Number Of Occurrences Of A Substring - Leetcode Solution

Problem Statement:

You are given a string s, and an integer k. You are required to find the maximum number of occurrences of a substring, such that the substring appears in s at least k times.

Solution:

To solve this problem, we can use the concept of binary search. We can start by first iterating over all the possible lengths of the substring, and then check if there exists a substring of that length, which appears at least k times in the given string.

Since we are looking for the maximum occurrences of a substring, we can use binary search to find the length of the substring with the maximum occurrences. We start with the lower bound of 1 and upper bound of the length of the string.

In the binary search loop, for each mid point between the left and right bounds, we need to check if there exists a substring of length mid, which appears at least k times in the given string. For this, we can use a sliding window approach, where we maintain a window of size mid on the given string and count the number of occurrences of each substring of size mid within the window.

If we find a substring of length mid, which appears at least k times in the given string, we can move our lower bound to mid + 1 and continue our binary search in the upper half of the bounds. Otherwise, we continue our search in the lower half of the bounds.

Finally, we return the maximum number of occurrences of a substring, which we would have obtained during the binary search.

The time complexity of this solution is O(nlogn), where n is the length of the given string.

Code:

class Solution {
public:
    int maxFreq(string s, int k) {
        int n = s.size();
        int left = 1, right = n, ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (check(s, k, mid)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
    
    bool check(string &s, int k, int len) {
        unordered_map<string, int> mp;
        for (int i = 0; i + len <= s.size(); i++) {
            string sub = s.substr(i, len);
            if (++mp[sub] == k) {
                return true;
            }
        }
        return false;
    }
};

1