LongestSubstringWithoutRepeatingCharacters.java

import java.util.HashMap;

/**
 * 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 class LongestSubstringWithoutRepeatingCharacters {
	public int lengthOfLongestSubstring(String s) {
		if (s.length() == 0)
			return 0;
		int i = 0, j = 0;
		int result = 0;
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		while (j < s.length()) {
			Integer c = new Integer(s.charAt(j));
			if (!map.containsKey(c)) {
				map.put(c, j);
			} else {
				int length = j - i;
				if (result < length) {
					result = length;
				}
				Integer index = map.get(c);
				i = Math.max(i, index + 1);
				map.put(c, j);
			}
			j++;
		}

		if (result < j - i)
			return j - i;
		else
			return result;
	}
}