3. Longest Substring Without Repeating Characters

Description

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.

Solutions

Solution 1: Two pointers + Hash Table

Define a hash table to record the characters in the current window. Let $i$ and $j$ represent the start and end positions of the non-repeating substring, respectively. The length of the longest non-repeating substring is recorded by ans.

For each character $s[j]$ in the string s, we call it $c$. If $c$ exists in the window $s[i..j-1]$, we move $i$ to the right until $s[i..j-1]$ does not contain c. Then we add c to the hash table. At this time, the window $s[i..j]$ does not contain repeated elements, and we update the maximum value of ans.

Finally, return ans.

The time complexity is $O(n)$, where $n$ represents the length of the string s.

Two pointers algorithm template:

for (int i = 0, j = 0; i < n; ++i) {
while (j < i && check(j, i)) {
++j;
}
// logic of specific problem
}

• class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> ss;
int i = 0, ans = 0;
for (int j = 0; j < s.size(); ++j) {
while (ss.count(s[j])) ss.erase(s[i++]);
ss.insert(s[j]);
ans = max(ans, j - i + 1);
}
return ans;
}
};

• class Solution:
def lengthOfLongestSubstring(self, s): # map for index
d = {} # value => its index
i = 0
ans = 0
for j, c in enumerate(s):
if c in d:
# mast max check i, example "abba"
i = max(i, d[c] + 1)
d[c] = j
ans = max(ans, j - i + 1)
return ans

class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:

if not s:
return 0

l = 0  # left
r = 0  # right

result = 0
isFoundInWindow = [False] * 256

while r < len(s):

while isFoundInWindow[ord(s[r])]:
isFoundInWindow[ord(s[l])] = False
l += 1

isFoundInWindow[ord(s[r])] = True

# check before shrink
result = max(result, r - l + 1)

r += 1

return result

class Solution: # extra space for set()
def lengthOfLongestSubstring(self, s: str) -> int:

d = collections.defaultdict(int)
start = 0
ans = 0
for i,c in enumerate(s):
# shrink
while d[c] > 0:
d[s[start]] -= 1 # not s[start], not start
start += 1
ans = max(ans, i - start + 1)
d[c] = 1
return ans

############

class Solution(object):
def _lengthOfLongestSubstring(self, s): # no extra data structure
"""
:type s: str
:rtype: int
"""
d = collections.defaultdict(int)
l = ans = 0
for i, c in enumerate(s):
while l > 0 and d[c] > 0:
d[s[i - l]] -= 1
l -= 1
d[c] += 1
l += 1
ans = max(ans, l)
return ans

############

class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ss = set()
i = ans = 0
for j, c in enumerate(s):
while c in ss:
ss.remove(s[i])
i += 1
ans = max(ans, j - i + 1)
return ans


• func lengthOfLongestSubstring(s string) int {
ss := map[byte]bool{}
i, ans := 0, 0
for j := 0; j < len(s); j++ {
for ss[s[j]] {
ss[s[i]] = false
i++
}
ss[s[j]] = true
ans = max(ans, j-i+1)
}
return ans
}

• function lengthOfLongestSubstring(s: string): number {
let ans = 0;
const vis = new Set<string>();
for (let i = 0, j = 0; i < s.length; ++i) {
while (vis.has(s[i])) {
vis.delete(s[j++]);
}
ans = Math.max(ans, i - j + 1);
}
return ans;
}


• /**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
const ss = new Set();
let i = 0;
let ans = 0;
for (let j = 0; j < s.length; ++j) {
while (ss.has(s[j])) {
ss.delete(s[i++]);
}
ans = Math.max(ans, j - i + 1);
}
return ans;
};


• class Solution {
/**
* @param String $s * @return Integer */ function lengthOfLongestSubstring($s) {
$max = 0; for ($i = 0; $i < strlen($s); $i++) {$chars = [];
$sub = ''; for ($j = $i;$j < strlen($s);$j++) {
if (in_array($s[$j], $chars)) { break; }$sub .= $s[$j];
$chars[] =$s[$j]; } if (strlen($sub) > $max) {$max = strlen($sub); } } return$max;
}
}

• public class Solution {
public int LengthOfLongestSubstring(string s) {
var ss = new HashSet<char>();
int i = 0, ans = 0;
for (int j = 0; j < s.Length; ++j)
{
while (ss.Contains(s[j]))
{
ss.Remove(s[i++]);
}
ans = Math.Max(ans, j - i + 1);
}
return ans;
}
}

• proc lengthOfLongestSubstring(s: string): int =
var
i = 0
j = 0
res = 0
literals: set[char] = {}

while i < s.len:
while s[i] in literals:
if s[j] in literals:
excl(literals, s[j])
j += 1
literals.incl(s[i]) # Uniform Function Call Syntax f(x) = x.f
res = max(res, i - j + 1)
i += 1

result = res # result has the default return value

echo lengthOfLongestSubstring("abcddabcf")


• use std::collections::HashSet;

impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let s = s.as_bytes();
let mut set = HashSet::new();
let mut i = 0;
s
.iter()
.map(|c| {
while set.contains(&c) {
set.remove(&s[i]);
i += 1;
}
set.insert(c);
set.len()
})
.max()
.unwrap_or(0) as i32
}
}


• class Solution {
func lengthOfLongestSubstring(_ s: String) -> Int {
var map = [Character: Int]()
var currentStartingIndex = 0
var i = 0
var maxLength = 0
for char in s {
if map[char] != nil {
if map[char]! >= currentStartingIndex {
maxLength = max(maxLength, i - currentStartingIndex)
currentStartingIndex = map[char]! + 1
}
}
map[char] = i
i += 1
}
return max(maxLength, i - currentStartingIndex)
}
}