Longest Substring Without Repeating Characters

Question

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

Example

For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.

For "bbbbb" the longest substring is "b", with the length of 1.

Challenge

O(n) time

Tags

String Two Pointers Hash Table

Related Problems

Medium Longest Substring with At Most K Distinct Characters

Analysis

for (i = 0; i < n; i++) {
while (j < n) {
if (满足条件)
j++
更行j状态
else (不满足条件)
break
}
更新i状态
}

Solution

public class Solution {
/**
* @param s: a string
* @return: an integer
*/
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
HashSet<Character> hs = new HashSet<Character>();
int ans = 0;

int i = 0;
int j = 0;
for (i = 0; i < s.length(); i++) {
while (j < s.length() && !hs.contains(s.charAt(j))) {
ans = Math.max(ans, j - i + 1);
j++;
}

hs.remove(s.charAt(i));
}
return ans;
}
}

LeetCode official: HashMap + Two Pointers

Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.

Complexity Analysis

• Time complexity :O(n)O(n). Indexjjwill iteratenntimes.

• Space complexity (HashMap) :O(min(m,n))O(min(m,n)). Same as the previous approach.

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;
}
}