五百年前

package com.sea.leetcode;

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

/**
 * Created by Kings on 2016/11/19.
 * 问题描述：
 * 返回一个给定的字符串的最长子字符串的长度。例如：
 * "Hello"  --->输出：3
 * 解题思路：
 * （1）用两个for循环去遍历所有子符串，将其长度放到list中，最后遍历一遍list取出最大值，即为最大长度。
 * 该方法的时间复杂度是O(log(n^2))，慢，不能通过leetcode测试。
 * （2）这个问题其实O(N)算法就够了，记录重复字符串的位置，然后相减得到一个长度，跟最大长度比较。当遍历一遍字符串时，
 * 最大值就出来了。
 *
 */
public class LongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        //Transform string to char array
        char[] carr = s.toCharArray();
        int carrLength = carr.length;
        int maxSubStrLength = 0;
        int subStrLength;
        int lastDupPosition = 0;

        //Use hash map to store each character
        Map<Character, Integer> characterMap = new HashMap<Character, Integer>();
        for (int i = 0; i < carrLength; i++) {
            Integer position = characterMap.get(carr[i]);
            if (position != null && position >= lastDupPosition) {
                lastDupPosition = position + 1;
            }
            subStrLength = i - lastDupPosition + 1;
            characterMap.put(carr[i], i);
            if (subStrLength > maxSubStrLength) {
                maxSubStrLength = subStrLength;
            }
        }
        return maxSubStrLength;
    }

    public static void main(String[] args) {
        String str = "aaa";

        System.out.println(str.length());
        LongestSubstring longestSubstring = new LongestSubstring();
        System.out.println(new Date().getTime());
        int time = longestSubstring.lengthOfLongestSubstring(str);
        System.out.println(new Date().getTime());
        System.out.println(time);
    }
}