LeetCode 3. Longest Substring Wi

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

Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

大致意思就是给定一个字符串s，返回s的最长无重复字符子串的长度。
解决该题目最高效的方法是使用HashMap保存字符最近一次出现的位置。遍历每个字符时添加它到一个已有的无重复字符子串结尾，如果这个字符之前出现过，用HashMap查询它出现的位置，如果它已经在这个无重复字符子串中，更新子串的起点使这个字符加到子串末尾后仍保持无重复字符。通过这种方式，遍历一次字符串，就可以得到所有的无重复字符子串，统计它们的长度选出最大的即可。
如果n为字符串的长度，m为字符的编码范围。
下面代码的时间复杂度为O(n)，空间复杂度为O(min(m, n)).

public class Solution {
    public int lengthOfLongestSubstring(String s) {

        Map<Character, Integer> latestIndex = new HashMap<>();  // 存放字符最近一次出现的位置
        int curStart = 0, curLen = 0, maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);  // 添加字符c到一个已有的无重复字符子串结尾
            if (latestIndex.containsKey(c) && latestIndex.get(c) >= curStart) { // 字符c已经在这个无重复字符子串中
                curStart = latestIndex.get(c) + 1;  // 更新当前无重复字符子串的起点
            }
            curLen = i - curStart + 1;  // 当前无重复字符子串的长度
            if (curLen > maxLen) {
                maxLen = curLen;
            }
            latestIndex.put(c, i);
        }
        return maxLen;
    }
}

如果已知字符编码范围很小，我们可以使用整型数组代替上面的HashMap
整型数组大小对应的字符编码范围如下

• int[26] for Letters 'a' - 'z' or 'A' - 'Z'
• int[128] for ASCII
• int[256] for Extended ASCII

下面代码的时间复杂度为O(n)，空间复杂度为O(m).

public class Solution {
    public int lengthOfLongestSubstring(String s) {

        int[] latestIndex = new int[256];   // 存放字符最近一次出现的位置
        for (int i = 0; i < 256; i++) {
            latestIndex[i] = -1;
        }
        int curStart = 0, curLen = 0, maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);   // 添加字符c到一个已有的无重复字符子串结尾
            if (latestIndex[c] >= curStart) {   // 字符c已经在这个无重复字符子串中
                curStart = latestIndex[c] + 1;  // 更新当前无重复字符子串的起点
            }
            curLen = i - curStart + 1;          // 当前无重复字符子串的长度
            if (curLen > maxLen) {
                maxLen = curLen;
            }
            latestIndex[c] = i;
        }
        return maxLen;
    }
}