Longest Substring Without Repeating Characters

LeetCode Q 3 - Longest Substring Without Repeating Characters

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

Solution

The solution is intuitional. Use two pointers applying sliding window algorithm and sweeping the whole string, then find the max length.

We can use a HashSet or an array to detect repeated character.

Method 1: Use a HashSet

Code:

public int lengthOfLongestSubstring(String s) {
	if (nums == null || nums.length == 0) return 0;
	Set<Character> seen = new HashSet<>();
	int maxLen = 0;
	for (int l = 0, r = 0; r < s.length(); ) {
		if (!seen.contains(s.charAt(r))) {
			seen.add(s.charAt(r++));
			maxLen = Math.max(maxLen, set.size());
		} else {
			seen.remove(s.charAt(l++));
		}
	}
	return maxLen;
}

Runtime: 9ms.

Method 2: Use an array

Code:

public int lengthOfLongestSubstring(String s) {
	if (nums == null || nums.length == 0) return 0;
	int[] count = new int[256];
	int maxLen = 0;
	for (int l = 0, r = 0; r < s.length(); r++) {
		count[s.charAt(r)]++;
		while (count[s.charAt(r)] > 1)
			count[s.charAt(l++)]--;
		maxLen = Math.max(maxLen, r - l + 1);
	}
	return maxLen;
}

Runtime: 3ms.