3.Longest-Substring-Without-Repeating-Characters

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.

代码

Approach 1: Sliding Window

Complexity Analysis
  • Time complexity : O(2n)
  • Space complexity : O(min(m, n))
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
} else {
set.remove(s.charAt(i++));
}
}
return ans;
}
}

Approach 2: Sliding Window Optimized

map: Character => Index
conatians character => update i
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)) + 1, i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j);
}
return ans;
}
}
int[128] 代替 map: Character => index
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128];
for (int j = 0, i = 0; j < n; j++) { abbcde
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1; // 为什么 j+1 => 当遇到i元素去重后, 取下一位
}
return ans;
}
}

Approach 3: Brute Force

Intuition
Check all the substring one by one to see if it has no duplicate character.
Complexity
  • Time complexity: O(n^3)
  • Space complexity: O(min(n,m)), The size of the Set is upper bounded by the size of the string n and the size of the charset/alphabet m.
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; i <= 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;
set.add(ch);
}
return true;
}
}