✅ [Python] Simple Solution w/ Explanation | Brute-Force + Sliding Window
We are given a string s. We need to find the length of the longest substring without repeating characters.\n\n\n\u2705 Solution I - Brute-Force [Accepted]\n\nSt
We are given a string `s`. We need to find the length of the **longest substring** without repeating characters.\n___\n___\n\u2705 **Solution I - Brute-Force [Accepted]**\n\nStarting with each index, we can check all substrings till we find a repeating character.\n\n```python\nclass Solution:\n    def lengthOfLongestSubstring(self, s: str) -> int:\n        res = 0\n        seen = set()\n        for start_idx in range(len(s)):\n            seen.clear()\n            end_idx = start_idx\n            while end_idx < len(s):\n                if s[end_idx] in seen:\n                    break\n                seen.add(s[end_idx])\n                end_idx += 1\n            res = max(res, end_idx - start_idx)\n        return res\n```\n\n- **Time Complexity:** `O(n\xB2)`\n- **Space Complexity:** `O(1)`\n___\n\u2705 **Solution II - Sliding Window [Accepted]**\n\nIn the above solution, we are doing many redundant operations. After finding a repeating character, we break the inner loop and again check for all substrings from the next index.\nThe following example will make it clear what I mean by redundant operations:\n\n```text\ns = "redundant"\nLet start_idx = 0\nWhen end_idx becomes 5, it sees that "d" had already come before.\nSo, should we start again with index 1?\nNo, because all substrings starting with "e" and later (till "d" or the character which was repeated) will have less length than that of "redun".\nWe can start from "u"\n```\n\nWe can create a sliding window: `[start_idx: end_idx]` where `end_idx` will move forward continuously and `start_idx` will change only if the character at `end_idx` is already present within this window. To know whether this character is already present, we need to store information about the index of characters.\n\n```python\nclass Solution:\n    def lengthOfLongestSubstring(self, s: str) -> int:\n        prev = [-1] * 128\n        res, start_idx = 0, 0\n        for end_idx, char in enumerate(s):\n            if prev[ord(char)] >= start_idx:\n                start_idx = prev[ord(char)] + 1\n            prev[ord(char)] = end_idx\n            res = max(res, end_idx - start_idx + 1)\n            \n        return res\n```\n\n- **Time Complexity:** `O(n)`\n- **Space Complexity:** `O(1)`\n\n___\n___\nIf you like the solution, please **upvote** \uD83D\uDD3C\nFor any questions, or discussions, comment below. \uD83D\uDC47\uFE0F\n
['Two Pointers', 'Sliding Window', 'Python', 'Python3']