O(n) | Beats 100 % | Sliding Window | Java | C++ | Python | Go | Rust | JavaScript
Intuition\n\nThe problem asks us to find the length of the longest substring without repeating characters. It might sound a bit technical at first, but we can b
## Intuition\n\nThe problem asks us to find the length of the **longest substring without repeating characters**. It might sound a bit technical at first, but we can break it down: \nImagine you\u2019re given a string, like "abcabcbb". What we\u2019re really being asked is, "What\u2019s the longest continuous chunk of this string where no characters repeat?" For example, in "abcabcbb", the substring "abc" is the longest part where every character is different. So, in this case, the answer would be 3 because "abc" is made up of 3 unique characters.\nWe\'re looking for the longest substring without repeating characters - seems simple enough, right? But We need to find a stretch of characters where each character appears only once it gets tricky when you have repeating characters in the string, like in the case of "abcabcbb". As soon as you hit the second \'a\', the substring is no longer valid because the \'a\' already appeared earlier. So, we\u2019ll need to figure out how to handle those situations without missing the longest valid substring. That\'s our target. The challenge here is that we need to do this efficiently - we can\'t just check every possible substring, especially if the string is really long.\n\nOur first instinct might be to use a brute force approach. We could check every possible substring, right? Start with the first character, then look at the first two, then the first three, and so on. For each substring, we\'d check if it has any repeating characters. But let\'s think about this for a moment. For a string of length n, we\'d be checking n(n+1)/2 substrings, and for each substring, we\'d need to scan through its characters to check for duplicates. That\'s an O(n^3) time complexity - definitely not efficient, especially for longer strings!\n\nSo, we need to refine our approach. This is where the concept of a sliding window comes in handy. Instead of checking every substring from scratch, what if we "slide" over the string, expanding or shrinking our window as we go? The window represents the current substring we\'re looking at, and we try to keep it as long as possible while ensuring there are no repeating characters inside it.\n\nLet\'s walk through this with an example, say "abcabcbb":\n\n1. We start with \'a\'. Our window is just "a" - no repeats, so we\'re good.\n2. We move to \'b\'. Window becomes "ab" - still no repeats.\n3. Next is \'c\'. Window is "abc" - all unique so far.\n4. Now we hit another \'a\'. Here\'s where it gets interesting. We can\'t just add this \'a\' to our window because it would create a repeat. So, we need to shrink our window from the left until we remove the first \'a\'.\n\nThis is a key insight: when we see a repeating character, we don\'t need to start all over. We can just adjust our window by moving the left boundary. This lets us keep track of longer substrings without recomputing everything from scratch.\n\n![1.png](https://assets.leetcode.com/users/images/5b7bec34-333f-4cf5-9afd-49e067aa3a0b_1726933738.8377316.png)\n\n\nBut Every time we hit a repeat, we\'re sliding the left side of the window one character at a time until the repeat is gone.  What if we could jump directly to the right position instead of sliding one by one? We need a way to quickly know where we last saw each character. A hash map could work, but remember, we\'re dealing with characters here. There\'s only a limited number of possible characters. we can use an array instead of a hash map, with each index representing a character. It\'s like having a direct line to where we last saw each character. This array will store the last seen position of each character we encounter.\n\n![2.png](https://assets.leetcode.com/users/images/e393d5df-3898-4b7d-9f80-945fd4032da4_1726933760.2353666.png)\n\n\nNow, let\'s think about how we\'d use this array. As we move through the string with our end pointer, we\'re updating our array with the latest position of each character. But here\'s the magic - we can use this same array to update our start pointer. When we hit a repeated character, instead of slowly shrinking the window, we can jump our start pointer directly to the position after where we last saw the repeated character.\n\nBut what if we\'ve already moved past the last occurrence of the repeated character? We don\'t want to jump backwards, do we? This is where we use a max operation. We set our start pointer to the max of its current position and the position after where we last saw the repeated character. This ensures we\'re always moving forward, never backward.\n\n![3.png](https://assets.leetcode.com/users/images/05428eb3-cb75-41fe-aea7-a4613a089f0a_1726933802.502143.png)\n\n\nAs we\'re doing all this, we\'re constantly updating our max length. Every time we move our end pointer, we check if this new substring is longer than our current max. It\'s like we\'re always ready to capture the longest substring at any moment.\n\nLet\'s think about edge cases for a moment. What if the string is empty? Or what if it\'s all the same character? Our approach handles these naturally. If it\'s empty, we never enter our loop. If it\'s all the same character, our max length will be 1.\n\nSo:\n\n>1. We keep two pointers - start and end - representing our current window.\n>2. We maintain an array (let\'s call it lastIndex) to store the last seen position of each character.\n>3. As we move the end pointer through the string:\n\t   - If the character at end is already in lastIndex and its position is after or at start, we need to jump start to skip over it.\n\t   - We update lastIndex with the current position of the character.\n\t   - We calculate the length of the current valid window (end - start + 1) and update our max length if needed.\n>4. We continue this until end reaches the end of the string.\n\nIt only requires one pass through the string. We\'re doing all our work - updating last seen positions, moving our start pointer, and calculating our max length - all in one smooth motion through the string. In terms of space complexity, we\'re using a fixed-size array for our characters. This is much more efficient than storing substrings or using a variable-size data structure. Our time complexity is O(n) because we\'re only scanning through the string once, making this solution efficient even for very long strings.\n\n## Approach\n\nAs i have already told in the intuition that core idea behind our solution is to use a sliding window approach combined with character indexing. This allows us to efficiently scan through the string once while keeping track of the longest valid substring we\'ve encountered so far.\n\nThe sliding window technique involves maintaining two pointers:\n1. A \'start\' pointer that marks the beginning of our current substring.\n2. An \'end\' pointer that we move through the string, expanding our substring.\n\nAs we move the \'end\' pointer, we\'re essentially expanding our window. When we encounter a repeated character, we need to contract our window by moving the \'start\' pointer.\n\nTo  handle repeated characters, we use an array to keep track of the last seen position of each character. This allows us to quickly jump our \'start\' pointer to the correct position when we encounter a repeat, rather than moving it incrementally.\n\n![1.png](https://assets.leetcode.com/users/images/afd84683-1deb-461d-a38a-051236569f63_1726935224.8451877.png)\n\n\n### Initialization\n\n```\nn = length of s\nmaxLength = 0\nlastIndex = array of 128 integers, all initialized to 0\nstart = 0\n```\n\n- We store the length of the input string in `n` for easy reference.\n- `maxLength` will keep track of the longest valid substring we\'ve seen so far.\n- `lastIndex` is an array used to store the last seen position of each character. We use 128 as the size because it covers all ASCII characters. Each index in this array represents a character, and the value at that index represents the last position where we saw that character.\n- `start` is initialized to 0, representing the start of our sliding window.\n\n### Main Loop\n\n```\nfor end = 0 to n-1:\n    currentChar = s[end]\n    start = max(start, lastIndex[currentChar])\n    maxLength = max(maxLength, end - start + 1)\n    lastIndex[currentChar] = end + 1\n```\n\n We iterate through the string, moving our \'end\' pointer from left to right.\n\n1. `currentChar = s[end]`: We get the current character at the \'end\' position.\n\n2. `start = max(start, lastIndex[currentChar])`: This is a crucial step. We update our \'start\' pointer to be the maximum of its current value and the last seen position of the current character plus one.\n\n   - If we haven\'t seen this character before (or if we\'ve seen it, but it\'s outside our current window), `lastIndex[currentChar]` will be less than `start`, so `start` remains unchanged.\n   - If we have seen this character within our current window, `lastIndex[currentChar]` will be greater than or equal to `start`. In this case, we move `start` to the position just after where we last saw this character.\n\n   This step effectively "jumps" our start pointer to the correct position when we encounter a repeat, ensuring our window always contains unique characters.\n\n3. `maxLength = max(maxLength, end - start + 1)`: We update `maxLength` if our current window is longer than the previous longest substring.\n\n4. `lastIndex[currentChar] = end + 1`: We update the last seen position of the current character. We use `end + 1` instead of `end` because it simplifies our logic in step 2 - it allows us to move `start` directly to the correct position without needing to add 1.\n\n## Pseudo-code Algorithm\n\n\n```\nfunction lengthOfLongestSubstring(s):\n    n = length of s\n    maxLength = 0\n    lastIndex = array of 128 integers, all initialized to 0\n    start = 0\n    \n    for end = 0 to n-1:\n        currentChar = s[end]\n        start = max(start, lastIndex[currentChar])\n        maxLength = max(maxLength, end - start + 1)\n        lastIndex[currentChar] = end + 1\n    \n    return maxLength\n```\n\n\n The longest substring without repeating characters ending at any position must be built from a valid substring ending at the previous position. By maintaining a sliding window, we\'re always building on our previous valid substrings. By using the `lastIndex` array, we can update our `start` pointer in constant time whenever we encounter a repeat. This is much more efficient than scanning back through the substring to find the repeated character. We only need to go through the string once. At each step, we\'re making a constant number of operations (updating `start`, `maxLength`, and `lastIndex`), resulting in a linear time complexity. We\'re using a fixed-size array for `lastIndex`, regardless of the input size. This gives us constant space complexity.\n\n## Time and Space Complexity\n\n- **Time Complexity: $O(n)$**, where n is the length of the input string. We make a single pass through the string, performing constant-time operations at each step.\n- **Space Complexity: $O(1)$**. We use a fixed-size array of 128 integers, regardless of the input size. This is considered constant space.\n\n\n\n## Code\n```java []\nclass Solution {\n    public int lengthOfLongestSubstring(String s) {\n        int n = s.length();\n        int maxLength = 0;\n        int[] lastIndex = new int[128];\n        \n        for (int start = 0, end = 0; end < n; end++) {\n            char currentChar = s.charAt(end);\n            start = Math.max(start, lastIndex[currentChar]);\n            maxLength = Math.max(maxLength, end - start + 1);\n            lastIndex[currentChar] = end + 1;\n        }\n        \n        return maxLength;\n    }\n}\n//KDS\n```\n\n```C++ []\nclass Solution {\npublic:\n    int lengthOfLongestSubstring(string s) {\n        int n = s.length();\n        int maxLength = 0;\n        vector<int> lastIndex(128, 0);\n        \n        for (int start = 0, end = 0; end < n; end++) {\n            char currentChar = s[end];\n            start = max(start, lastIndex[currentChar]);\n            maxLength = max(maxLength, end - start + 1);\n            lastIndex[currentChar] = end + 1;\n        }\n        \n        return maxLength;\n    }\n};\n```\n```Python []\nclass Solution:\n    def lengthOfLongestSubstring(self, s: str) -> int:\n        n = len(s)\n        max_length = 0\n        last_index = {}\n        \n        start = 0\n        for end in range(n):\n            current_char = s[end]\n            start = max(start, last_index.get(current_char, 0))\n            max_length = max(max_length, end - start + 1)\n            last_index[current_char] = end + 1\n        \n        return max_length\n```\n```Go []\nfunc lengthOfLongestSubstring(s string) int {\n    n := len(s)\n    maxLength := 0\n    lastIndex := make([]int, 128)\n    \n    start := 0\n    for end := 0; end < n; end++ {\n        currentChar := s[end]\n        if lastIndex[currentChar] > start {\n            start = lastIndex[currentChar]\n        }\n        if end-start+1 > maxLength {\n            maxLength = end - start + 1\n        }\n        lastIndex[currentChar] = end + 1\n    }\n    \n    return maxLength\n}\n```\n```Rust []\nimpl Solution {\n    pub fn length_of_longest_substring(s: String) -> i32 {\n        let mut max_length = 0;\n        let mut last_index = [0; 128];\n        let mut start = 0;\n        \n        for (end, ch) in s.chars().enumerate() {\n            start = start.max(last_index[ch as usize]);\n            max_length = max_length.max(end - start + 1);\n            last_index[ch as usize] = end + 1;\n        }\n        \n        max_length as i32\n    }\n}\n```\n```JavaScript []\n/**\n * @param {string} s\n * @return {number}\n */\nvar lengthOfLongestSubstring = function(s) {\n    let n = s.length;\n    let maxLength = 0;\n    let lastIndex = new Map();\n    \n    let start = 0;\n    for (let end = 0; end < n; end++) {\n        let currentChar = s[end];\n        start = Math.max(start, lastIndex.get(currentChar) || 0);\n        maxLength = Math.max(maxLength, end - start + 1);\n        lastIndex.set(currentChar, end + 1);\n    }\n    \n    return maxLength;\n};\n```\n\n\n## Example\n#### Example 1: **"abcabcbb"**\n\n![1.png](https://assets.leetcode.com/users/images/ce8545f4-4481-479d-9206-b39d45058de7_1726936524.0809677.png)\n\n| Step | `end` | `start` | `currentChar` | `lastIndex[currentChar]` | `new start` | `window` | `maxLength` |\n|------|-------|---------|---------------|--------------------------|-------------|----------|-------------|\n| 1    | 0     | 0       | \'a\'           | 0                        | 0           | "a"      | 1           |\n| 2    | 1     | 0       | \'b\'           | 0                        | 0           | "ab"     | 2           |\n| 3    | 2     | 0       | \'c\'           | 0                        | 0           | "abc"    | 3           |\n| 4    | 3     | 0       | \'a\'           | 1                        | 1           | "bca"    | 3           |\n| 5    | 4     | 1       | \'b\'           | 2                        | 2           | "cab"    | 3           |\n| 6    | 5     | 2       | \'c\'           | 3                        | 3           | "abc"    | 3           |\n| 7    | 6     | 3       | \'b\'           | 5                        | 5           | "b"      | 3           |\n| 8    | 7     | 5       | \'b\'           | 6                        | 6           | "b"      | 3           |\n\n**Result:** The maximum valid window without repeating characters is `"abc"`, with a length of `3`.\n\n\n#### Example 2: **"bbbbb"**\n\n![2.png](https://assets.leetcode.com/users/images/3918d857-57fb-4e30-8756-047618424ff9_1726936556.1592152.png)\n\n\n| Step | `end` | `start` | `currentChar` | `lastIndex[currentChar]` | `new start` | `window` | `maxLength` |\n|------|-------|---------|---------------|--------------------------|-------------|----------|-------------|\n| 1    | 0     | 0       | \'b\'           | 0                        | 0           | "b"      | 1           |\n| 2    | 1     | 0       | \'b\'           | 1                        | 1           | "b"      | 1           |\n| 3    | 2     | 1       | \'b\'           | 2                        | 2           | "b"      | 1           |\n| 4    | 3     | 2       | \'b\'           | 3                        | 3           | "b"      | 1           |\n| 5    | 4     | 3       | \'b\'           | 4                        | 4           | "b"      | 1           |\n\n**Result:** The longest substring without repeating characters is `"b"`, with a length of `1`.\n\n\n\n\n#### Example 3: **"pwwkew"**\n\n![exampl3.png](https://assets.leetcode.com/users/images/2a801cd7-70c9-4821-a029-6e72d7ceec77_1727022927.2044847.png)\n\n\n| Step | `end` | `start` | `currentChar` | `lastIndex[currentChar]` | `new start` | `window` | `maxLength` |\n|------|-------|---------|---------------|--------------------------|-------------|----------|-------------|\n| 1    | 0     | 0       | \'p\'           | 0                        | 0           | "p"      | 1           |\n| 2    | 1     | 0       | \'w\'           | 0                        | 0           | "pw"     | 2           |\n| 3    | 2     | 0       | \'w\'           | 2                        | 2           | "w"      | 2           |\n| 4    | 3     | 2       | \'k\'           | 0                        | 2           | "wk"     | 2           |\n| 5    | 4     | 2       | \'e\'           | 0                        | 2           | "wke"    | 3           |\n| 6    | 5     | 2       | \'w\'           | 3                        | 3           | "kew"    | 3           |\n\n**Result:** The longest substring without repeating characters is `"wke"` or `"kew"`, both with a length of `3`.
['Hash Table', 'Sliding Window', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript']