1
Software Development

## 【Day 25】#3 - Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

``````Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
``````

Example 2:

``````Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
``````

Example 3:

``````Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
``````

## 解法一(Brute Force)

``````public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j <= n; j++)
if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
return ans;
}

public boolean allUnique(String s, int start, int end) {
Set<Character> set = new HashSet<>();
for (int i = start; i < end; i++) {
Character ch = s.charAt(i);
if (set.contains(ch)) return false;
}
return true;
}
}
``````

## 解法二(Sliding Window)

``````public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}
``````
``````class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
str_list = []
max_length = 0

for x in s:
if x in str_list:
str_list = str_list[str_list.index(x)+1:]

str_list.append(x)
max_length = max(max_length, len(str_list))

return max_length
``````

LeetCode刷題日記30