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.