mediumStringsPattern: Sliding Window
Longest Substring with Limited Frequency Diversity Solution
Problem Statement
You are given a string s consisting of lowercase English letters, and an integer k. A substring is considered valid if the number of distinct frequencies of the characters present in that substring is at most k. Return the maximum length of a valid substring of s. Characters that do not appear in the substring are not counted towards the distinct frequencies.
Examples
Example 1:
Input:s = "aabbacb", k = 1
Output:4
Explanation: The substring "aabb" has a length of 4. The characters present are 'a' (frequency 2) and 'b' (frequency 2). The set of distinct frequencies is {2}, which has size 1. Since 1 <= k, this is a valid substring.
Example 2:
Input:s = "abcde", k = 2
Output:5
Explanation: The entire string "abcde" has a length of 5. The only character frequency present is 1. The set of distinct frequencies is {1}, which has size 1. Since 1 <= k, this is valid.
Constraints
- 1 <= s.length <= 5 * 10^4
- 1 <= k <= 26
- s consists only of lowercase English letters.
Time: O(n) Space: O(1)
Using a sliding window with two maps (one for char frequencies, one for frequency-of-frequencies) allows constant time updates as the window expands and shrinks. This reduces the time complexity to O(n) because each character is added and removed from the window at most once.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.