0340 solved.

liuyubobobo · liuyubobobo · commit d277c238ba41 · 2019-02-23T18:01:02.000-08:00
diff --git a/0340-Longest-Substring-with-At-Most-K-Distinct-Characters/cpp-0340/CMakeLists.txt b/0340-Longest-Substring-with-At-Most-K-Distinct-Characters/cpp-0340/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.13)
+project(cpp_0340)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_0340 main.cpp)
diff --git a/0340-Longest-Substring-with-At-Most-K-Distinct-Characters/cpp-0340/main.cpp b/0340-Longest-Substring-with-At-Most-K-Distinct-Characters/cpp-0340/main.cpp
@@ -0,0 +1,53 @@
+/// 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;
+}
diff --git a/0340-Longest-Substring-with-At-Most-K-Distinct-Characters/cpp-0340/main2.cpp b/0340-Longest-Substring-with-At-Most-K-Distinct-Characters/cpp-0340/main2.cpp
@@ -0,0 +1,43 @@
+/// 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;
+}
diff --git a/readme.md b/readme.md
@@ -299,6 +299,8 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | | | | | | |
 | 337 | [House Robber III](https://leetcode.com/problems/house-robber-iii/description/) | [无] | [C++](0337-House-Robber-III/cpp-0337/) | | |
 | | | | | | |
+| 340 | [Longest Substring with At Most K Distinct Characters](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/) | [solution](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/solution/) | [C++](0340-Longest-Substring-with-At-Most-K-Distinct-Characters/cpp-0340/) | | |
+| | | | | | |
 | 343 | [Integer Break](https://leetcode.com/problems/integer-break/description/) | [无] | [C++](0343-Integer-Break/cpp-0343/) | [Java](0343-Integer-Break/java-0343/src/) | |
 | 344 | [Reverse String](https://leetcode.com/problems/reverse-string/description/) | [无] | [C++](0344-Reverse-String/cpp-0344/) | | |
 | 345 | [Reverse Vowels of a String](https://leetcode.com/problems/reverse-vowels-of-a-string/description/) | [无] | [C++](0345-Reverse-Vowels-of-a-String/cpp-0345/) | | |
