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.
Table of Contents
- Problem Statement
- Longest Substring Without Repeating Characters solution in C++
- Longest Substring Without Repeating Characters soution in Java
- Longest Substring Without Repeating Characters solution Python
- Additional Resources
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
Additional Resources
- Explore all Leetcode problems solutions at Progiez here
- Explore all problems on Leetcode website here
Feel free to give suggestions! Contact Us