Longest Substring Without Repeating Characters LeetCode problem Solution

Longest Substring (WRC) LeetCode Problem Solution

In this post, we are going to  Longest Substring Without Repeating Characters LeetCode problem which is related to arrays and Hash Table. Let’s have a look at the problem statement first and then try to solve the problem.

Longest Substring Without Repeating Characters LeetCode Problem Statement

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.

 Longest Substring Without Repeating Characters Problem Solutions

I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.

Problem Solution in JavaScript

var k = 0;
    var maxLength = 0;
    for(i = 0; i < s.length; i++) {
        for (j = k; j < i; j++) {
            if (s[i] === s[j]) {
                k = j + 1;
                break;
            }
        }
        if (i - k + 1 > maxLength) {
            maxLength = i - k + 1;
        }
    }
    return maxLength;

Problem Solution in C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans=0,l=0,r=0;
        int  n =s.size();
        vector<int> map(256,-1);
        while(r<n){
            if(map[s[r]]!=-1){
                l=max(map[s[r]]+1,l);
            }
            map[s[r]]=r;
            ans= max(ans,r-l+1);
            r++;
        }
        return ans;
    }
};

Problem Solution in Python

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        ans, l, r = 0, 0, 0
        n = len(s)
        map = [-1] * 256
        while r < n:
            if map[ord(s[r])] != -1:
                l = max(map[ord(s[r])] + 1, l)
            map[ord(s[r])] = r
            ans = max(ans, r - l + 1)
            r += 1
        return ans