Longest Substring Without Repeating Characters - LeetCode

Problem

Given a string, find the length of the longest substring without repeating characters. 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.


	public static int lengthOfLongestSubstring(String s) {
	}

public static int lengthOfLongestSubstring(String s) {

}

Solution

The approach is to scan the string from left one by one. If a duplicate character is found and its recent position is greater than the start position, then adjust the start position.

Time complexity: O(n)
Space: O(1)

Example:

Code example:


	public static int lengthOfLongestSubstring(String s) {
		int max = 0;
		int start = 0;
		int end = 0;
		// character -- index mapping
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		
		for(int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if(map.containsKey(c) && map.get(c) >= start) {
				start = map.get(c) + 1;
			} 
			map.put(c, i); // current position of the character
			end = i;
			max = max > (end - start + 1) ? max : end - start + 1;
		}
		
		return max;
	}

public static int lengthOfLongestSubstring(String s) {

int max = 0;

int start = 0;

int end = 0;

// character -- index mapping

Map<Character, Integer> map = new HashMap<Character, Integer>();

for(int i = 0; i < s.length(); i++) {

char c = s.charAt(i);

if(map.containsKey(c) && map.get(c) >= start) {

start = map.get(c) + 1;

}

map.put(c, i); // current position of the character

end = i;

max = max > (end - start + 1) ? max : end - start + 1;

}

return max;

}

or using an Array to record character position


    public int lengthOfLongestSubstring(String s) {
		int max = 0;
		int start = 0;
		int end = 0;
		int[] char_positions = new int[256];  // record character latest position
		
		for(int i = 0; i < 256; i++) {
			char_positions[i] = -1; // initialize to -1
		}
		
		for(int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			// the most important part, when to move the start point
			if(char_positions[c] != -1 && char_positions[c] >= start) {  
				start = char_positions[c] + 1; 
			}
			char_positions[c] = i;  // current position of the character
			end = i;
			max = max > (end - start + 1) ? max : end - start + 1;
		}
		
		return max;
    }