Longest Substring Without Repeating Characters
Finding Longest Substring Without Repeating Characters
Given a string s, your task is to find the length of the longest substring that contains only unique characters, meaning no character repeats within this substring.
A substring is defined as a continuous block of characters within the string, and it must maintain the original order of characters.
For example, in the string “abcabcbb”, the longest substring without repeating characters is “abc”, which has a length of 3.
The goal is to determine the length of such a substring for any given input.
Output: 3
Explanation : The string “xyz” is the longest without duplicate characters.
Output: 1
Constraints:
- 0 <= s.length <= 1000
- s may consist of printable ASCII characters.
Finding Longest Substring Solution
Recommendation for Time and Space Complexity – You should aim for a solution with O(n) time and O(m) space, where n is the length of the string and m is the number of unique characters in the string.
Hints for solving problems
Hint 1 :
A brute force solution would be to try the substring starting at index i and try to find the maximum length we can form without duplicates by starting at that index. we can use a hash set to detect duplicates in O(1) time. Can you think of a better way?
Hint 2 :
We can use the sliding window algorithm. Since we only care about substrings without duplicate characters, the sliding window can help us maintain valid substring with its dynamic nature.
There are mainly 3 approach to solve this problem-
- Brute Force Method
- Sliding Window Method
- Sliding Window Mehtod(Optimal)
1. Brute Force Method
Generate all possible substrings, check each substring for unique characters, and keep track of the maximum length.
- Time complexity: O(n*m)
- Space complexity: O(m)
where n is the length of the string and m is the total number of unique characters in the string.
Code
class Solution { public: int lengthOfLongestSubstring(string s) { int res = 0; for (int i = 0; i < s.size(); i++) { unordered_setcharSet; for (int j = i; j < s.size(); j++) { if (charSet.find(s[j]) != charSet.end()) { break; } charSet.insert(s[j]); } res = max(res, (int)charSet.size()); } return res; } };
public class Solution { public int lengthOfLongestSubstring(String s) { int res = 0; for (int i = 0; i < s.length(); i++) { SetcharSet = new HashSet<>(); for (int j = i; j < s.length(); j++) { if (charSet.contains(s.charAt(j))) { break; } charSet.add(s.charAt(j)); } res = Math.max(res, charSet.size()); } return res; } }
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: res = 0 for i in range(len(s)): charSet = set() for j in range(i, len(s)): if s[j] in charSet: break charSet.add(s[j]) res = max(res, len(charSet)) return res
class Solution { /** * @param {string} s * @return {number} */ lengthOfLongestSubstring(s) { let res = 0; for (let i = 0; i < s.length; i++) { let charSet = new Set(); for (let j = i; j < s.length; j++) { if (charSet.has(s[j])) { break; } charSet.add(s[j]); } res = Math.max(res, charSet.size); } return res; } }
2. Sliding Window Method
Use two pointers to create a dynamic window that adjusts based on character repetition. Slide the window by removing characters from the start until all characters in the current window are unique.
- Time complexity: O(n)
- Space complexity: O(m)
where n is the length of the string and m is the total number of unique characters in the string.
Code
class Solution { public: int lengthOfLongestSubstring(string s) { unordered_setcharSet; int l = 0; int res = 0; for (int r = 0; r < s.size(); r++) { while (charSet.find(s[r]) != charSet.end()) { charSet.erase(s[l]); l++; } charSet.insert(s[r]); res = max(res, r - l + 1); } return res; } };
public class Solution { public int lengthOfLongestSubstring(String s) { HashSetcharSet = new HashSet<>(); int l = 0; int res = 0; for (int r = 0; r < s.length(); r++) { while (charSet.contains(s.charAt(r))) { charSet.remove(s.charAt(l)); l++; } charSet.add(s.charAt(r)); res = Math.max(res, r - l + 1); } return res; } }
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: charSet = set() l = 0 res = 0 for r in range(len(s)): while s[r] in charSet: charSet.remove(s[l]) l += 1 charSet.add(s[r]) res = max(res, r - l + 1) return res
class Solution { /** * @param {string} s * @return {number} */ lengthOfLongestSubstring(s) { const charSet = new Set(); let l = 0; let res = 0; for (let r = 0; r < s.length; r++) { while (charSet.has(s[r])) { charSet.delete(s[l]); l++; } charSet.add(s[r]); res = Math.max(res, r - l + 1); } return res; } }
3. Sliding Window Method(Optimal)
Use a hash set or map to store characters and their positions, adjusting the window efficiently whenever a duplicate is found. This method ensures a time complexity of O(n).
- Time complexity: O(n)
- Space complexity: O(m)
where n is the length of the string and m is the total number of unique characters in the string.
Code
class Solution { public: int lengthOfLongestSubstring(string s) { unordered_mapmp; int l = 0, res = 0; for (int r = 0; r < s.size(); r++) { if (mp.find(s[r]) != mp.end()) { l = max(mp[s[r]] + 1, l); } mp[s[r]] = r; res = max(res, r - l + 1); } return res; } };
public class Solution { public int lengthOfLongestSubstring(String s) { HashMapmp = new HashMap<>(); int l = 0, res = 0; for (int r = 0; r < s.length(); r++) { if (mp.containsKey(s.charAt(r))) { l = Math.max(mp.get(s.charAt(r)) + 1, l); } mp.put(s.charAt(r), r); res = Math.max(res, r - l + 1); } return res; } }
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: mp = {} l = 0 res = 0 for r in range(len(s)): if s[r] in mp: l = max(mp[s[r]] + 1, l) mp[s[r]] = r res = max(res, r - l + 1) return res
class Solution { /** * @param {string} s * @return {number} */ lengthOfLongestSubstring(s) { let mp = new Map(); let l = 0, res = 0; for (let r = 0; r < s.length; r++) { if (mp.has(s[r])) { l = Math.max(mp.get(s[r]) + 1, l); } mp.set(s[r], r); res = Math.max(res, r - l + 1); } return res; } }