# Longest Substring Without Repeating Characters **Difficulty:** MEDIUM [External](https://leetcode.com/problems/longest-substring-without-repeating-characters) Canonical: https://scaleengineer.com/dsa/problems/longest-substring-without-repeating-characters **Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window) **Data structures:** Hash Table, String **Companies:** [AMD](https://scaleengineer.com/companies/amd), [Accenture](https://scaleengineer.com/companies/accenture), [Accolite](https://scaleengineer.com/companies/accolite), [Adobe](https://scaleengineer.com/companies/adobe), [Agoda](https://scaleengineer.com/companies/agoda), [Amazon](https://scaleengineer.com/companies/amazon), [American Express](https://scaleengineer.com/companies/american-express), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cisco](https://scaleengineer.com/companies/cisco), [Cognizant](https://scaleengineer.com/companies/cognizant), [Comcast](https://scaleengineer.com/companies/comcast), [Deloitte](https://scaleengineer.com/companies/deloitte), [Docusign](https://scaleengineer.com/companies/docusign), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Epic Systems](https://scaleengineer.com/companies/epic-systems), [Expedia](https://scaleengineer.com/companies/expedia), [Flipkart](https://scaleengineer.com/companies/flipkart), [FreshWorks](https://scaleengineer.com/companies/freshworks), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Grab](https://scaleengineer.com/companies/grab), [HCL](https://scaleengineer.com/companies/hcl), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nagarro](https://scaleengineer.com/companies/nagarro), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Ozon](https://scaleengineer.com/companies/ozon), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [PayPal](https://scaleengineer.com/companies/paypal), [Paytm](https://scaleengineer.com/companies/paytm), [Publicis Sapient](https://scaleengineer.com/companies/publicis-sapient), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Roblox](https://scaleengineer.com/companies/roblox), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Snowflake](https://scaleengineer.com/companies/snowflake), [Spotify](https://scaleengineer.com/companies/spotify), [TikTok](https://scaleengineer.com/companies/tiktok), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wipro](https://scaleengineer.com/companies/wipro), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Yelp](https://scaleengineer.com/companies/yelp), [ZScaler](https://scaleengineer.com/companies/zscaler), [Zoho](https://scaleengineer.com/companies/zoho), [athenahealth](https://scaleengineer.com/companies/athenahealth), [eBay](https://scaleengineer.com/companies/ebay), [persistent systems](https://scaleengineer.com/companies/persistent-systems), [tcs](https://scaleengineer.com/companies/tcs), [josh technology](https://scaleengineer.com/companies/josh-technology), [Airtel](https://scaleengineer.com/companies/airtel), [Alibaba](https://scaleengineer.com/companies/alibaba), [Coupang](https://scaleengineer.com/companies/coupang), [Dell](https://scaleengineer.com/companies/dell), [Freecharge](https://scaleengineer.com/companies/freecharge), [HPE](https://scaleengineer.com/companies/hpe), [Juspay](https://scaleengineer.com/companies/juspay), [Lucid Motors](https://scaleengineer.com/companies/lucid-motors), [Lyft](https://scaleengineer.com/companies/lyft), [MAQ Software](https://scaleengineer.com/companies/maq-software), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [NCR](https://scaleengineer.com/companies/ncr), [Netflix](https://scaleengineer.com/companies/netflix), [Nike](https://scaleengineer.com/companies/nike), [Optum](https://scaleengineer.com/companies/optum), [PornHub](https://scaleengineer.com/companies/pornhub), [SOTI](https://scaleengineer.com/companies/soti), [Salesforce](https://scaleengineer.com/companies/salesforce), [Softwire](https://scaleengineer.com/companies/softwire), [Tesla](https://scaleengineer.com/companies/tesla), [ThoughtWorks](https://scaleengineer.com/companies/thoughtworks), [Turing](https://scaleengineer.com/companies/turing), [Veeva Systems](https://scaleengineer.com/companies/veeva-systems), [Virtusa](https://scaleengineer.com/companies/virtusa), [Zeta](https://scaleengineer.com/companies/zeta), [Zynga](https://scaleengineer.com/companies/zynga), [opentext](https://scaleengineer.com/companies/opentext) --- ## Problem Given a string `s`, find the length of the **longest** **substring** without duplicate 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. # Approaches ## Brute Force This approach checks every possible substring to see if it contains unique characters and keeps track of the maximum length found. **Time:** O(n³) · **Space:** O(min(n, m)) where n is the length of the string and m is the size of the character set. **Pros:** Simple to understand and implement. **Cons:** Highly inefficient due to its cubic time complexity.; Redundant computations as it re-evaluates overlapping substrings multiple times. ### Explanation The brute-force method involves generating all substrings of the given string `s`. For each substring, we then verify if it contains any duplicate characters. To generate all substrings, we use two nested loops. The outer loop fixes the starting index `i`, and the inner loop fixes the ending index `j`. For each substring from `i` to `j`, a helper function is used to check for uniqueness. This function typically uses a `HashSet` to store characters of the current substring. If a character is encountered that is already in the set, the substring is not unique. Otherwise, if the entire substring is traversed without finding duplicates, it's valid, and we update our maximum length. ```java class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int maxLength = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (allUnique(s, i, j)) { maxLength = Math.max(maxLength, j - i + 1); } } } return maxLength; } private boolean allUnique(String s, int start, int end) { Set set = new HashSet<>(); for (int i = start; i <= end; i++) { char ch = s.charAt(i); if (set.contains(ch)) { return false; } set.add(ch); } return true; } } ``` ### Algorithm - Initialize `maxLength = 0`. - Use a loop with index `i` from `0` to `s.length() - 1` to select the starting character of the substring. - Use a nested loop with index `j` from `i` to `s.length() - 1` to select the ending character of the substring. - For each substring `s.substring(i, j + 1)`, check if all its characters are unique. - To check for uniqueness, use a `HashSet`. Iterate from `i` to `j`, adding `s.charAt(k)` to the set. If a character is already present, the substring has duplicates. - If the substring has unique characters, update `maxLength = Math.max(maxLength, j - i + 1)`. - After all substrings are checked, return `maxLength`. ## Sliding Window with a Set This approach uses a sliding window, represented by two pointers, to find the longest valid substring. A `HashSet` is used to keep track of characters within the current window. **Time:** O(n) · **Space:** O(min(n, m)) where n is the length of the string and m is the size of the character set. **Pros:** Significantly more efficient than brute force with linear time complexity.; Intuitive application of the sliding window pattern. **Cons:** The left pointer `i` might move multiple times for a single move of `j`, leading to more operations than the optimized version, although the asymptotic complexity remains the same. ### Explanation A more efficient approach is to use the sliding window technique. A window is a range of indices `[i, j]` that represents the current substring being considered. We use a `HashSet` to store the characters in the current window. We start with an empty window (`i=0`). We iterate through the string with a right pointer `j`, trying to expand the window. If the character `s.charAt(j)` is not in our set, we add it and expand the window. The length of this new valid window is `j - i + 1`, and we update our `maxLength`. If `s.charAt(j)` is already in the set, it means we have a duplicate. To fix this, we must shrink the window from the left by incrementing the left pointer `i` and removing `s.charAt(i)` from the set. We repeat this until the window is valid again (i.e., `s.charAt(j)` is no longer a duplicate in the window `[i, j]`). ```java import java.util.HashSet; import java.util.Set; class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int maxLength = 0; int i = 0; Set set = new HashSet<>(); for (int j = 0; j < n; j++) { char c = s.charAt(j); while (set.contains(c)) { set.remove(s.charAt(i)); i++; } set.add(c); maxLength = Math.max(maxLength, j - i + 1); } return maxLength; } } ``` ### Algorithm - Initialize two pointers `i = 0` (start of window) and `j = 0` (end of window), and `maxLength = 0`. - Initialize a `HashSet` to store characters in the current window. - Iterate with the `j` pointer from `0` to `s.length() - 1`: - While the character `s.charAt(j)` is already in the set: - Remove `s.charAt(i)` from the set. - Increment `i`. - Add `s.charAt(j)` to the set. - Update `maxLength = Math.max(maxLength, j - i + 1)`. - After the loop, return `maxLength`. ## Optimized Sliding Window with a Map/Array This is the most optimal approach. It improves upon the basic sliding window by using a `HashMap` or an integer array to store the last seen indices of characters. This allows the window's start pointer to jump directly to the required position, avoiding incremental shrinking. **Time:** O(n) · **Space:** O(m) where m is the size of the character set. This can be considered O(1) for fixed sets like ASCII. **Pros:** Most efficient solution with O(n) time complexity.; True single-pass algorithm where each pointer moves forward only.; Constant space complexity O(m) if the character set is fixed. **Cons:** Slightly more complex to reason about the pointer jump compared to the basic sliding window. ### Explanation This approach refines the sliding window technique for maximum efficiency. Instead of just knowing *if* a character is in the window, we need to know *where* its last occurrence was. A `HashMap` (or an integer array for a fixed character set like ASCII) is used to store the most recent index of each character encountered. We iterate through the string with a right pointer `j`. For each character `s.charAt(j)`, we check if it has been seen before. If it has, and its last seen index is within our current window (i.e., greater than or equal to the left pointer `i`), we have a duplicate in the current window. Instead of shrinking the window one by one, we can directly jump the left pointer `i` to the position right after the previous occurrence of `s.charAt(j)`. This immediately makes the window valid again. After potentially updating `i`, we calculate the length of the current valid window (`j - i + 1`) and update our `maxLength`. Finally, we update the last seen index of `s.charAt(j)` in our map/array to the current index `j`. ```java import java.util.HashMap; import java.util.Map; class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int maxLength = 0; Map charIndexMap = new HashMap<>(); int i = 0; // start of the window for (int j = 0; j < n; j++) { char currentChar = s.charAt(j); if (charIndexMap.containsKey(currentChar)) { // Move the start of the window (i) to the right of the last // occurrence of the current character. // We use Math.max to ensure i doesn't move backward if we find // a character whose last occurrence was before the current window's start. i = Math.max(charIndexMap.get(currentChar) + 1, i); } maxLength = Math.max(maxLength, j - i + 1); charIndexMap.put(currentChar, j); } return maxLength; } } ``` ### Algorithm - Initialize `maxLength = 0` and a left pointer `i = 0`. - Initialize a `HashMap` to map characters to their last seen indices. Alternatively, for a fixed character set like ASCII, an integer array `int[128]` can be used for better performance. - Iterate through the string with a right pointer `j` from `0` to `s.length() - 1`. - Let `currentChar = s.charAt(j)`. - If `currentChar` exists in the map, it means we've seen it before. Update the left pointer `i = Math.max(i, map.get(currentChar) + 1)`. This ensures `i` only moves forward and jumps past the last occurrence of `currentChar`. - Calculate the length of the current window: `j - i + 1`. - Update `maxLength = Math.max(maxLength, j - i + 1)`. - Update the last seen index of `currentChar` in the map: `map.put(currentChar, j)`. - After the loop, return `maxLength`. # Solutions ### CSharp ```csharp public class Solution { public int LengthOfLongestSubstring(string s) { var ss = new HashSet < char > (); int i = 0, ans = 0; for (int j = 0; j < s.Length; ++j) { while (ss.Contains(s[j])) { ss.Remove(s[i++]); } ss.Add(s[j]); ans = Math.Max(ans, j - i + 1); } return ans; } } ``` ### Java ```java for ( int i = 0 , j = 0 ; i < n ; ++ i ) { while ( j < i && check ( j , i )) { ++ j ; } // logic of specific problem } ``` ### JavaScript ```javascript /** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function (s) { const ss = new Set(); let i = 0; let ans = 0; for (let j = 0; j < s.length; ++j) { while (ss.has(s[j])) { ss.delete(s[i++]); } ss.add(s[j]); ans = Math.max(ans, j - i + 1); } return ans; }; ``` ### CPP ```cpp class Solution { public: int lengthOfLongestSubstring(string s) { unordered_set ss; int i = 0, ans = 0; for (int j = 0; j < s.size(); ++j) { while (ss.count(s[j])) ss.erase(s[i++]); ss.insert(s[j]); ans = max(ans, j - i + 1); } return ans; } }; ``` ### Python ```python class Solution: def lengthOfLongestSubstring(self, s): # map for index d = {} # value => its index i = 0 ans = 0 for j , c in enumerate ( s ): if c in d : # mast max check i, example "abba" i = max ( i , d [ c ] + 1 ) d [ c ] = j ans = max ( ans , j - i + 1 ) return ans class Solution : def lengthOfLongestSubstring ( self , s : str ) -> int : if not s : return 0 l = 0 # left r = 0 # right result = 0 isFoundInWindow = [ False ] * 256 while r < len ( s ): while isFoundInWindow [ ord ( s [ r ])]: isFoundInWindow [ ord ( s [ l ])] = False l += 1 isFoundInWindow [ ord ( s [ r ])] = True # check before shrink result = max ( result , r - l + 1 ) r += 1 return result class Solution : # extra space for set() def lengthOfLongestSubstring ( self , s : str ) -> int : d = collections . defaultdict ( int ) start = 0 ans = 0 for i , c in enumerate ( s ): # shrink while d [ c ] > 0 : d [ s [ start ]] -= 1 # not s[start], not start start += 1 ans = max ( ans , i - start + 1 ) d [ c ] = 1 return ans ############ class Solution ( object ): def _lengthOfLongestSubstring ( self , s ): # no extra data structure """ :type s: str :rtype: int """ d = collections . defaultdict ( int ) l = ans = 0 for i , c in enumerate ( s ): while l > 0 and d [ c ] > 0 : d [ s [ i - l ]] -= 1 l -= 1 d [ c ] += 1 l += 1 ans = max ( ans , l ) return ans ############ class Solution : def lengthOfLongestSubstring ( self , s : str ) -> int : ss = set () i = ans = 0 for j , c in enumerate ( s ): while c in ss : ss . remove ( s [ i ]) i += 1 ss . add ( c ) ans = max ( ans , j - i + 1 ) return ans ```