Algorithm


Problem Name: 3. Longest Substring Without Repeating Characters
 
Given a string s, find the length of the longest substring (A substring is a contiguous non-empty sequence of characters within a string.) 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.

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


int lengthOfLongestSubstring(char* s) {
    int i, j, l, k = 0;
    char c;
    int pos[128] = { 0 };
    char *p;
    int n = 0;

    for (i = 0; s[i]; i ++) {
        n ++;
        c = s[i];
        l = i - pos[c] + 1;
        pos[c] = i + 1;
        n = n  <  l ? n : l;
        k = k > n ? k : n;
    }

    return k;
}

Copy The Code & Try With Live Editor

Input

x
+
cmd
s = "abcabcbb"

Output

x
+
cmd
3

#2 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_mapm;
        int maxlen = 0;
        for(int i = 0, j = 0; j  <  s.size(); j++){
            m[s[j]]++;
            while(m[s[j]] > 1) m[s[i++]]--;
            maxlen = max(maxlen, j - i + 1);
        }
        return maxlen;
    }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
s = "bbbbb"

Output

x
+
cmd
1

#3 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int lengthOfLongestSubstring(String s) {
    int start = 0;
    int end = 0;
    int n = s.length();
    Map < Character, Integer> map = new HashMap<>();
    int maxLength = 0;
    while (end  <  n) {
      char c = s.charAt(end++);
      map.put(c, map.getOrDefault(c, 0) + 1);
      while (start  < = end && map.get(c) > 1) {
        map.put(s.charAt(start), map.getOrDefault(s.charAt(start++), 0) - 1);
      }
      maxLength = Math.max(maxLength, end - start);
    }
    return maxLength;
  }
}

Copy The Code & Try With Live Editor

Input

x
+
cmd
s = "pwwkew"

Output

x
+
cmd
3

#4 Code Example with Javascript Programming

Code - Javascript Programming


const lengthOfLongestSubstring = function(s) {
  if(s.length < 2) return s.length
  const hash = {}
  let max = 0
  for(let i = 0, j = -1, len = s.length; i  <  len; i++) {
    const cur = s[i]
    if(hash[cur] != null) j = Math.max(j, hash[cur])
    
    hash[cur] = i
    max = Math.max(max, i - j>
  }
  
  return max
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
s = "abcabcbb"

Output

x
+
cmd
3

#5 Code Example with Python Programming

Code - Python Programming


class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        mx, start, chars = 0, 0, {}
        for i in range(len(s)):
            if s[i] in chars and start <= chars[s[i]]: start = chars[s[i]] + 1
            else: mx = max(mx, i - start + 1)
            chars[s[i]] = i
        return mx
Copy The Code & Try With Live Editor

Input

x
+
cmd
s = "bbbbb"

Output

x
+
cmd
1

#6 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;

namespace LeetCode
{
    public class _003_LongestSubstringWithoutRepeatingCharacters
    {
        public int LengthOfLongestSubstring(string s)
        {
            if (string.IsNullOrEmpty(s)) return 0;

            var map = new Dictionary < int, int>();
            var maxLen = 0;
            var lastRepeatPos = -1;
            for (int i = 0; i  <  s.Length; i++)
            {
                if (map.ContainsKey(s[i]) && lastRepeatPos < map[s[i]])
                    lastRepeatPos = map[s[i]];
                if (maxLen  <  i - lastRepeatPos)
                    maxLen = i - lastRepeatPos;
                map[s[i]] = i;
            }

            return maxLen;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
"abcabcbb"

Output

x
+
cmd
3
Advertisements

Demonstration


Previous
#02 Leetcode Add two numbers solution in JavaScript, C, PHP, C++, Java, C#, Python Programming, PHP, Python
Next
#04 Leetcode Median of Two Sorted Arrays Solution in C, C++, Java, JavaScript, Python, C# Leetcode