Longest Substring Without Repeating Characters Leetcode Solution
Longest Substring Without Repeating CharactersLeetcode Problem :
Given a string s, find the length of the longest substring without repeating characters.
A substring is a contiguous non-empty sequence of characters within a string.
Longest Substring Without Repeating Characters Leetcode Solution :
Constraints :
- 0 <= s.length <= 5 * 104.
- s consists of English letters, digits, symbols and spaces.
Example 1:
Input:s = “bbbbb”Output: 1
Example 2:
Input: s = “pwwkew”Output: 3
Intuition:
To solve this problem we would use HashMap and sliding window algorithm
Explanation:
We declare HashMap to calculate longest substring with unique characters, then we declare count, max and left pointer, we loop with right pointer for each char in s string untiol we get not unique char in our window, then we enter into while loop and loop with left pointer decrementing chars in our map, and decrement counter variable until we left with all unique character in our hashmap, then we exit while loop, at end of each iteration of right pointer we set max of count and prev count value.
Complexity :
Time Complexity : O(n)
Space Complexity : O(n)
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length();
int maxLength = 0;
unordered_map charMap;
int left = 0;
for (int right = 0; right < n; right++) {
if (charMap.count(s[right]) == 0 || charMap[s[right]] < left) {
charMap[s[right]] = right;
maxLength = max(maxLength, right - left + 1);
} else {
left = charMap[s[right]] + 1;
charMap[s[right]] = right;
}
}
return maxLength;
}
};
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int maxLength = 0;
Map charMap = new HashMap<>();
int left = 0;
for (int right = 0; right < n; right++) {
if (!charMap.containsKey(s.charAt(right)) || charMap.get(s.charAt(right)) < left) {
charMap.put(s.charAt(right), right);
maxLength = Math.max(maxLength, right - left + 1);
} else {
left = charMap.get(s.charAt(right)) + 1;
charMap.put(s.charAt(right), right);
}
}
return maxLength;
}
}
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
maxLength = 0
charMap = {}
left = 0
for right in range(n):
if s[right] not in charMap or charMap[s[right]] < left:
charMap[s[right]] = right
maxLength = max(maxLength, right - left + 1)
else:
left = charMap[s[right]] + 1
charMap[s[right]] = right
return maxLength
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
