Solved problem 3 : Longest Substring Without Repeating Characters

racoelhosilva · racoelhosilva · commit fd3f6b4b7031 · 2024-02-03T10:08:55.000Z
diff --git a/README.md b/README.md
@@ -16,7 +16,7 @@
 
 ### Problems Solved
 
-| Total | 50 |
+| Total | 51 |
 |:---:|:---:|
 
 #### Search By Topic
@@ -37,7 +37,7 @@
 | Linked Lists | 5 |
 | Math & Geometry | 4 |
 | Priority Queue | 3 |
-| Sliding Window | 1 |
+| Sliding Window | 2 |
 | Stack | 2 |
 | Tries | 0 |
 | Two Pointers | 4 |
@@ -47,7 +47,7 @@
 | Difficulty | Number |
 |:---|---:|
 | Easy | 45 |
-| Medium | 5 |
+| Medium | 6 |
 | Hard | 0 |
 
 ## Milestones
diff --git a/Sliding Window/Medium/3_LongestSubstringWithoutRepeatingCharacters.cpp b/Sliding Window/Medium/3_LongestSubstringWithoutRepeatingCharacters.cpp
@@ -0,0 +1,48 @@
+/* 
+ * Problem: 3 
+ * Name: Longest Substring Without Repeating Characters
+ * Difficulty: Medium
+ * Topic: Sliding Window
+ * Link: https://leetcode.com/problems/longest-substring-without-repeating-characters/
+ */
+ 
+#include <bits/stdc++.h>
+using namespace std;
+
+//      Unordered Set
+// Time Complexity: O(n)
+// Space Complexity: O(n)
+int lengthOfLongestSubstringUS(string s) {
+    int result = 0;
+    int left = 0, right = 0;
+    unordered_set<char> chars;
+    while (right < s.size()){
+        while (chars.count(s[right]) > 0) {
+            chars.erase(s[left]);
+            left++;
+        }
+        chars.insert(s[right]);
+        result = max(result, right - left + 1);
+        right++;
+    }
+    return result;
+}
+
+//      Bool Vector
+// Time Complexity: O(n)
+// Space Complexity: O(256)
+int lengthOfLongestSubstringV(string s) {
+    int result = 0;
+    int left = 0, right = 0;
+    vector<bool> chars(256,0);
+    while (right < s.size()){
+        while (chars[s[right]]) {
+            chars[s[left]] = 0;
+            left++;
+        }
+        chars[s[right]] = 1;
+        result = max(result, right - left + 1);
+        right++;
+    }
+    return result;
+}
