Longest Substring Without Repeating Characters – Leetcode Solution

In this post, we are going to solve the 3. Longest Substring Without Repeating Characters problem of Leetcode. This problem 3. Longest Substring Without Repeating Characters is a Leetcode medium level problem. Let’s see code, 3. Longest Substring Without Repeating Characters.

Problem

Given a string s, find the length of the longest substring without repeating 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.

Now, let’s see the code of 3. Longest Substring Without Repeating Characters – Leetcode Solution.

Longest Substring Without Repeating Characters – Leetcode Solution

3. Longest Substring Without Repeating Characters – Solution in Java

class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), longest = 0;
int[] nextIndex = new int[128];

for (int r=0, l=0; r<n; r++) {
l = Math.max(nextIndex[s.charAt(r)], l);
longest = Math.max(longest, r - l + 1);
nextIndex[s.charAt(r)] = r + 1;
}

return longest;
}
}

3. Longest Substring Without Repeating Characters – Solution in C++

class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length(), longest = 0;
vector<int> nextIndex(128);

for (int r=0, l=0; r<n; r++) {
l = max(nextIndex[s[r]], l);
longest = max(longest, r - l + 1);
nextIndex[s[r]] = r + 1;
}

return longest;
}
};

3. Longest Substring Without Repeating Characters– Solution in Python

class Solution:
def lengthOfLongestSubstring(self, s):
start = maxLength = 0
usedChar = {}

for i in range(len(s)):
if s[i] in usedChar and start <= usedChar[s[i]]:
start = usedChar[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)

usedChar[s[i]] = i

return maxLength

Note: This problem 3. Longest Substring Without Repeating Characters is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.