3. Longest Substring Without Repeating Characters LeetCode Solution
In this guide we will provide 3. Longest Substring Without Repeating Characters LeetCode Solution with best time and space complexity. The solution to Longest Substring Without Repeating Characters problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.
Problem Statement of Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(128) = O(1)
3. Longest Substring Without Repeating Characters LeetCode Solution in C++
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0;
vector<int> count(128);
for (int l = 0, r = 0; r < s.length(); ++r) {
++count[s[r]];
while (count[s[r]] > 1)
--count[s[l++]];
ans = max(ans, r - l + 1);
}
return ans;
}
}; /* code provided by PROGIEZ */
3. Longest Substring Without Repeating Characters LeetCode Solution in Java
class Solution {
public int lengthOfLongestSubstring(String s) {
int ans = 0;
int[] count = new int[128];
for (int l = 0, r = 0; r < s.length(); ++r) {
++count[s.charAt(r)];
while (count[s.charAt(r)] > 1)
--count[s.charAt(l++)];
ans = Math.max(ans, r - l + 1);
}
return ans;
}
} // code provided by PROGIEZ
3. Longest Substring Without Repeating Characters LeetCode Solution in Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = 0
count = collections.Counter()
l = 0
for r, c in enumerate(s):
count[c] += 1
while count[c] > 1:
count[s[l]] -= 1
l += 1
ans = max(ans, r - l + 1)
return ans #code by PROGIEZ
