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 * 104sconsists 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;
}
Input
s = "abcabcbb"
Output
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;
}
};
Input
s = "bbbbb"
Output
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;
}
}
Input
s = "pwwkew"
Output
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
};
Input
s = "abcabcbb"
Output
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
Input
s = "bbbbb"
Output
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;
}
}
}
Input
"abcabcbb"
Output
3