package com.sid.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 3. Longest Substring Without Repeating Characters.
 *
 * <blockquote>
 * Given a string, find the length of the <b>longest substring</b> without repeating characters.
 *
 * <p>
 * <b>Examples:</b>
 * <p>Given <font color='#D02572'>"abcabcbb"</font>, the answer is <font color='#D02572'>"abc"</font>, which the length is 3.
 * <p>Given <font color='#D02572'>"bbbbb"</font>, the answer is <font color='#D02572'>"b"</font>, with the length of 1.
 * <p>Given <font color='#D02572'>"pwwkew"</font>, the answer is <font color='#D02572'>"wke"</font>, with the length of 3. Note that the answer must be a <b>substring</b>, "pwke" is a subsequence and not a substring.
 * </blockquote>
 *
 * @author Sid.Chen
 * @version 1.0, 2016-07-12
 *
 */
public class A0003_LongestSubstringWithoutRepeatingCharacters {

	public int lengthOfLongestSubstring(String s) {
		int answer = 0, start = 0;
		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) {
				answer = Math.max(answer, i - start);
				start = map.get(c) + 1;
			}
			map.put(c, i);
		}
        return Math.max(answer, s.length() - start);
    }

}

@@ -266,17 +266,18 @@
 %3EExample
-s
+ 1
 :%3C/b%3E%0A *
@@ -282,111 +282,121 @@
  * %3C
-p%3EGiven %3Cfont color='#D02572'%3E%22abcabcbb%22%3C/font%3E, the answer is %3Cfont color='#D02572'%3E%22abc%22%3C/font%3E, whic
+blockquote%3E%0A * %3Cb%3EInput:%3C/b%3E %22abcabcbb%22%0A * %3Cp%3E%3Cb%3EOutput:%3C/b%3E 3%0A * %3Cp%3E%3Cb%3EExplanation:%3C/b%3E The answer is %22abc%22, wit
 h th
@@ -408,18 +408,18 @@
 gth 
-is
+of
  3.%0A * %3C
 p%3EGi
@@ -418,100 +418,160 @@
  * %3C
-p%3EGiven %3Cfont color='#D02572'%3E%22bbbbb%22%3C/font%3E, the answer is %3Cfont color='#D02572'%3E%22b%22%3C/font%3E
+/blockquote%3E%0A * %0A * %3Cp%3E%0A * %3Cb%3EExample 2:%3C/b%3E%0A * %3Cblockquote%3E%0A * %3Cb%3EInput:%3C/b%3E %22bbbbb%22%0A * %3Cp%3E%3Cb%3EOutput:%3C/b%3E 1%0A * %3Cp%3E%3Cb%3EExplanation:%3C/b%3E The answer is %22b%22
 , wi
@@ -591,110 +591,170 @@
  of 
-1
+3
 .%0A * %3C
-p%3EGiven %3Cfont color='#D02572'%3E%22pwwkew%22%3C/font%3E, the answer is %3Cfont color='#D02572'%3E%22wke%22%3C/font%3E
+/blockquote%3E%0A * %0A * %3Cp%3E%0A * %3Cb%3EExample 3:%3C/b%3E%0A * %3Cblockquote%3E%0A * %3Cb%3EInput:%3C/b%3E %22pwwkew%22%0A * %3Cp%3E%3Cb%3EOutput:%3C/b%3E 3%0A * %3Cp%3E%3Cb%3EExplanation:%3C/b%3E The answer is %22wke%22
 , wi
@@ -772,17 +772,23 @@
 th of 3.
- 
+%0A * %3Cp%3E
 Note tha
@@ -890,16 +890,37 @@
 kquote%3E%0A
+ * %0A * %3C/blockquote%3E%0A
  *%0A * @a
@@ -1071,16 +1071,22 @@
 bstring(
+final 
 String s
@@ -1120,16 +1120,22 @@
  = 0;%0A%09%09
+final 
 Map%3CChar
@@ -1236,16 +1236,22 @@
 +) %7B%0A%09%09%09
+final 
 char c =

Clean up #3 Longest Substring Without Repeating Characters