Longest Substring with At Most K Distinct Characters Solutions in C++
Number 340
Difficulty Hard
Acceptance 44.1%
Link LeetCode
Other languages —
Solutions
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters//// Author : liuyubobobo/// Time : 2019-02-23#include <iostream>#include <unordered_map>#include <cassert>using namespace std;/// Sliding Window/// Time Complexity: O(n)/// Space Complexity: O(1)class Solution {public:int lengthOfLongestSubstringKDistinct(string s, int k) {if(!k) return 0;int l = 0, r = -1, res = 0;unordered_map<char, int> freq;while(r + 1 < s.size()){while(r + 1 < s.size() && ok(freq, s[r + 1], k))freq[s[r + 1]] ++, r ++;// assert(freq.size() == k);res = max(res, r - l + 1);while(l <= r && freq.size() >= k){freq[s[l]] --;if(freq[s[l]] == 0) freq.erase(s[l]);l ++;}}return res;}private:bool ok(const unordered_map<char, int>& freq, char c, int k){if(freq.size() <= k - 1) return true;assert(freq.size() == k);return freq.count(c);}};int main() {return 0;}
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters//// Author : liuyubobobo/// Time : 2019-02-23#include <iostream>#include <unordered_map>#include <cassert>using namespace std;/// Sliding Window (Another implement version)/// Time Complexity: O(n)/// Space Complexity: O(1)class Solution {public:int lengthOfLongestSubstringKDistinct(string s, int k) {if(!k) return 0;int l = 0, r = -1, res = 0;unordered_map<char, int> freq;while(r + 1 < s.size()){if(freq.size() < k || freq.count(s[r + 1]))freq[s[r + 1]] ++, r ++;else{freq[s[l]] --;if(freq[s[l]] == 0) freq.erase(s[l]);l ++;}res = max(res, r - l + 1);}return res;}};int main() {return 0;}