Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/3.html
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 * 10^{4}
s
consists of English letters, digits, symbols and spaces.
Algorithm
Given the example “abcabcbb,” the task is to find the longest substring without any repeating characters. This can be achieved by traversing the string character by character and maintaining a sliding window with no repeated characters. If a repeated character is encountered, the first occurrence of that character should be removed from the window.
To achieve this, we need to record the characters that have appeared before. One way to do this is to count the number of occurrences of each character. However, since the position of the character is important in this problem, we can use a HashMap to establish a mapping between each character and its last appearance position.
When considering how to record the character occurrences, we need to decide whether to save all occurrences or just record one location. The method we derived manually before is to maintain a sliding window with no repeated characters, and the size of the window needs to be enlarged as much as possible. Since the window is constantly sliding to the right, it only cares about the last position of each character and establishes a mapping.
To implement this approach, we can define a HashMap to create a mapping between each character and its last appearance position. We also need to define two variables, res
and left
, where res
is used to record the length of the longest nonrepeated substring, and left
points to the previous starting position of the nonrepeated substring on the left of the string. Since left
is the previous position of the left border of the window, it is initialized to 1.
Next, we traverse the entire string character by character. For each character, if the character already exists in the HashMap and its mapping value is greater than left
, we update left
to the current mapping value. Then, we update the mapping value to the current coordinate i
, which ensures that left
is always the previous position of the current boundary. Finally, we update the result res
with the length of the current window, which is i  left
.
The condition m.count(s[i]) && m[s[i]] > left
in the if
statement in the program checks whether the current character s[i]
has already been mapped in the HashMap. If so, it means that the character has already appeared before, and if m[s[i]] > left
is true, it means that the previous occurrence of this character is in the current window. In this case, to add the current repeated character, we need to remove the previous occurrence. To do so, we assign left
to m[s[i]]
, which is equivalent to moving the sliding window.
For example, when the string is “aa,” the mapping of a > 0
is established when i = 0
, and the result res
is updated to 1
. When i = 1
, the character a
is found in the HashMap, and the mapping value 0
is greater than 1
for left
. Therefore, we update left
to 0
and update the mapping pair to a > 1
. Then, i  left
is still 1
, so we don’t update the result res
. The final result res
is still 1
, which is correct.
Code

import java.util.HashMap; public class Longest_Substring_Without_Repeating_Characters { public static void main(String[] args) { Longest_Substring_Without_Repeating_Characters out = new Longest_Substring_Without_Repeating_Characters(); Solution s = out.new Solution(); int longest = s.lengthOfLongestSubstring("abcbefg"); System.out.println(longest); } // ref: https://leetcode.com/problems/longestsubstringwithoutrepeatingcharacters/solution/ class Solution_map { public int lengthOfLongestSubstring(String s) { if (s == null  s.length() == 0) { return 0; } int result = 0; HashMap<Character, Integer> hm = new HashMap<>(); for (int left = 0, right = 0; right < s.length(); right++) { char probeChar = s.charAt(right); if (hm.containsKey(probeChar)) { // mast max check i // example "abba", last 'a' will result in index 0 if not max checking left = Math.max(left, hm.get(probeChar) + 1); } hm.put(probeChar, right); result = Math.max(result, right  left + 1); } return result; } } // @note: remove the final check outside while loop, cleaner code, run time: 7ms. above method 16ms /* * optimization is: * 1. moving longest recording after * 2. no extra operation: removing first repeated char in inner while, then adding this char to set next looping * 3. "Math.max(j  i + 1, maxLen)" is cleaner than "x>y ? x:y" * */ class Solution { public int lengthOfLongestSubstring(String s) { if (s == null  s.length() == 0) { return 0; } int l = 0; // left int r = 0; // right int result = 0; boolean[] isFoundInWindow = new boolean[256]; while (r < s.length()) { while (isFoundInWindow[s.charAt(r)]) { isFoundInWindow[s.charAt(l)] = false; l++; } isFoundInWindow[s.charAt(r)] = true; // check before shrink result = Math.max(result, r  l + 1); r++; } return result; } } } ############ class Solution { public int lengthOfLongestSubstring(String s) { Set<Character> ss = new HashSet<>(); int i = 0, ans = 0; for (int j = 0; j < s.length(); ++j) { char c = s.charAt(j); while (ss.contains(c)) { ss.remove(s.charAt(i++)); } ss.add(c); ans = Math.max(ans, j  i + 1); } return ans; } }

// OJ: https://leetcode.com/problems/longestsubstringwithoutrepeatingcharacters/ // Time: O(N) // Space: O(C) where C is the range of character set // Ref: https://discuss.leetcode.com/topic/24739/ccodein9lines class Solution { public: int lengthOfLongestSubstring(string s) { int ans = 0, start = 1; vector<int> m(128, 1); for (int i = 0; i < s.size(); ++i) { start = max(start, m[s[i]]); m[s[i]] = i; ans = max(ans, i  start); } return ans; } };

class Solution: def lengthOfLongestSubstring(self, s): # map for index d = {} start = 0 ans = 0 for i, c in enumerate(s): if c in d: # mast max check start, example "abba" start = max(start, d[c] + 1) d[c] = i ans = max(ans, i  start + 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

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, ji+1) } return ans } func max(a, b int) int { if a > b { return a } return b }

function lengthOfLongestSubstring(s: string): number { 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++]); } ss.add(s[j]); ans = Math.max(ans, j  i + 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++]); } ss.add(s[j]); ans = Math.max(ans, j  i + 1); } return ans; };

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++]); } ss.Add(s[j]); 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) } }