✅3 Method's || C++ || JAVA || PYTHON || Beginner Friendly🔥🔥🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind the 3 solutions is to iteratively find the longest substring witho
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind the 3 solutions is to iteratively find the longest substring without repeating characters by maintaining a sliding window approach. We use two pointers (`left` and `right`) to represent the boundaries of the current substring. As we iterate through the string, we update the pointers and adjust the window to accommodate new unique characters and eliminate repeating characters.\n\n# Approach 1 - Set\n<!-- Describe your approach to solving the problem. -->\n\n1. We use a set (`charSet`) to keep track of unique characters in the current substring.\n2. We maintain two pointers, `left` and `right`, to represent the boundaries of the current substring.\n3. The `maxLength` variable keeps track of the length of the longest substring encountered so far.\n4. We iterate through the string using the `right` pointer.\n5. If the current character is not in the set (`charSet`), it means we have a new unique character.\n6. We insert the character into the set and update the `maxLength` if necessary.\n7. If the character is already present in the set, it indicates a repeating character within the current substring.\n8. In this case, we move the `left` pointer forward, removing characters from the set until the repeating character is no longer present.\n9. We insert the current character into the set and continue the iteration.\n10. Finally, we return the `maxLength` as the length of the longest substring without repeating characters.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int lengthOfLongestSubstring(string s) {\n        int n = s.length();\n        int maxLength = 0;\n        unordered_set<char> charSet;\n        int left = 0;\n        \n        for (int right = 0; right < n; right++) {\n            if (charSet.count(s[right]) == 0) {\n                charSet.insert(s[right]);\n                maxLength = max(maxLength, right - left + 1);\n            } else {\n                while (charSet.count(s[right])) {\n                    charSet.erase(s[left]);\n                    left++;\n                }\n                charSet.insert(s[right]);\n            }\n        }\n        \n        return maxLength;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int lengthOfLongestSubstring(String s) {\n        int n = s.length();\n        int maxLength = 0;\n        Set<Character> charSet = new HashSet<>();\n        int left = 0;\n        \n        for (int right = 0; right < n; right++) {\n            if (!charSet.contains(s.charAt(right))) {\n                charSet.add(s.charAt(right));\n                maxLength = Math.max(maxLength, right - left + 1);\n            } else {\n                while (charSet.contains(s.charAt(right))) {\n                    charSet.remove(s.charAt(left));\n                    left++;\n                }\n                charSet.add(s.charAt(right));\n            }\n        }\n        \n        return maxLength;\n    }\n}\n\n```\n```Python3 []\nclass Solution:\n    def lengthOfLongestSubstring(self, s: str) -> int:\n        n = len(s)\n        maxLength = 0\n        charSet = set()\n        left = 0\n        \n        for right in range(n):\n            if s[right] not in charSet:\n                charSet.add(s[right])\n                maxLength = max(maxLength, right - left + 1)\n            else:\n                while s[right] in charSet:\n                    charSet.remove(s[left])\n                    left += 1\n                charSet.add(s[right])\n        \n        return maxLength\n\n```\n\n# Approach 2 - Unordered Map\n1. We improve upon the first solution by using an unordered map (`charMap`) instead of a set.\n2. The map stores characters as keys and their indices as values.\n3. We still maintain the `left` and `right` pointers and the `maxLength` variable.\n4. We iterate through the string using the `right` pointer.\n5. If the current character is not in the map or its index is less than `left`, it means it is a new unique character.\n6 We update the `charMap` with the character\'s index and update the `maxLength` if necessary.\n7. If the character is repeating within the current substring, we move the `left` pointer to the next position after the last occurrence of the character.\n8. We update the index of the current character in the `charMap` and continue the iteration.\n9. At the end, we return the `maxLength` as the length of the longest substring without repeating characters.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int lengthOfLongestSubstring(string s) {\n        int n = s.length();\n        int maxLength = 0;\n        unordered_map<char, int> charMap;\n        int left = 0;\n        \n        for (int right = 0; right < n; right++) {\n            if (charMap.count(s[right]) == 0 || charMap[s[right]] < left) {\n                charMap[s[right]] = right;\n                maxLength = max(maxLength, right - left + 1);\n            } else {\n                left = charMap[s[right]] + 1;\n                charMap[s[right]] = right;\n            }\n        }\n        \n        return maxLength;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int lengthOfLongestSubstring(String s) {\n        int n = s.length();\n        int maxLength = 0;\n        Map<Character, Integer> charMap = new HashMap<>();\n        int left = 0;\n        \n        for (int right = 0; right < n; right++) {\n            if (!charMap.containsKey(s.charAt(right)) || charMap.get(s.charAt(right)) < left) {\n                charMap.put(s.charAt(right), right);\n                maxLength = Math.max(maxLength, right - left + 1);\n            } else {\n                left = charMap.get(s.charAt(right)) + 1;\n                charMap.put(s.charAt(right), right);\n            }\n        }\n        \n        return maxLength;\n    }\n}\n\n```\n```Python3 []\nclass Solution:\n    def lengthOfLongestSubstring(self, s: str) -> int:\n        n = len(s)\n        maxLength = 0\n        charMap = {}\n        left = 0\n        \n        for right in range(n):\n            if s[right] not in charMap or charMap[s[right]] < left:\n                charMap[s[right]] = right\n                maxLength = max(maxLength, right - left + 1)\n            else:\n                left = charMap[s[right]] + 1\n                charMap[s[right]] = right\n        \n        return maxLength\n\n```\n\n# Approach 3 - Integer Array\n1. This solution uses an integer array `charIndex` to store the indices of characters.\n2. We eliminate the need for an unordered map by utilizing the array.\n3. The `maxLength`, `left`, and `right` pointers are still present.\n4. We iterate through the string using the `right` pointer.\n5. We check if the current character has occurred within the current substring by comparing its index in `charIndex` with `left`.\n6. If the character has occurred, we move the `left` pointer to the next position after the last occurrence of the character.\n7. We update the index of the current character in `charIndex`.\n8. At each step, we update the `maxLength` by calculating the length of the current substring.\n9. We continue the iteration until reaching the end of the string.\n10. Finally, we return the `maxLength` as the length of the longest substring without repeating characters.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int lengthOfLongestSubstring(string s) {\n        int n = s.length();\n        int maxLength = 0;\n        vector<int> charIndex(128, -1);\n        int left = 0;\n        \n        for (int right = 0; right < n; right++) {\n            if (charIndex[s[right]] >= left) {\n                left = charIndex[s[right]] + 1;\n            }\n            charIndex[s[right]] = right;\n            maxLength = max(maxLength, right - left + 1);\n        }\n        \n        return maxLength;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int lengthOfLongestSubstring(String s) {\n        int n = s.length();\n        int maxLength = 0;\n        int[] charIndex = new int[128];\n        Arrays.fill(charIndex, -1);\n        int left = 0;\n        \n        for (int right = 0; right < n; right++) {\n            if (charIndex[s.charAt(right)] >= left) {\n                left = charIndex[s.charAt(right)] + 1;\n            }\n            charIndex[s.charAt(right)] = right;\n            maxLength = Math.max(maxLength, right - left + 1);\n        }\n        \n        return maxLength;\n    }\n}\n\n```\n```Python3 []\nclass Solution:\n    def lengthOfLongestSubstring(self, s: str) -> int:\n        n = len(s)\n        maxLength = 0\n        charIndex = [-1] * 128\n        left = 0\n        \n        for right in range(n):\n            if charIndex[ord(s[right])] >= left:\n                left = charIndex[ord(s[right])] + 1\n            charIndex[ord(s[right])] = right\n            maxLength = max(maxLength, right - left + 1)\n        \n        return maxLength\n\n```\n\n![CUTE_CAT.png](https://assets.leetcode.com/users/images/3831fd95-3bb1-44d1-bc1a-06b3b4317b56_1687028369.5286949.png)\n**If you found my solution helpful, I would greatly appreciate your upvote, as it would motivate me to continue sharing more solutions.**\n\n\n
['Hash Table', 'String', 'C++', 'Java', 'Python3']