最長無重複字元的子串--動态規劃

Longest Substring Without Repeating Characters：

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.

尋找最長無重複字元的子串

注：子串是完全相鄰的字元集合，而子序列是從左向右順序的不一定相鄰的字元集合，注意其差別

給定一個字元串，尋找其最長無重複字元的子串的長度

例如

“abcabcbb” –> “abc”, length = 3

“bbbbb” –> “b”, length = 1

“pwwkew” –> “wke”, length 3

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

        if (s==null || s.length() == ) return ;

        //記錄字元上一次出現的位置，ascii字元最多256個，是以長度為256
        int[] lastPosOfChar = new int[];
        //将上次此字元出現的位置初始化為-1，代表未出現過
        Arrays.fill(lastPosOfChar, -);
        int maxLength = ;    // 最長子串長度
        int startPos = ;     // 最長子串起始位置

        //采用動态規劃算法，将目标字元串周遊一遍，即可得出結果
        for (int i = ; i < s.length(); i++) {
            //如果目前字元未出現過或者字元上次出現的位置小于startPos，
            //則子串起始位置依然是startPos；
            //否則startPos便是上次出現此字元的位置+1
            startPos = (startPos > lastPosOfChar[s.charAt(i)])? startPos : (lastPosOfChar[s.charAt(i)] + );
            //字元周遊過後，便記錄其位置，
            //作為後面的相同字元出現時更新子串起始位置的憑據
            lastPosOfChar[s.charAt(i)] = i;
            //周遊過目前字元後，目前子串的無重複長度便為:i - startPos + 1
            //然後和過往的子串長度maxLength比較，保留最大值
            maxLength = (i - startPos +  > maxLength)? (i - startPos + ) : maxLength;

        }

        return maxLength;
    }
}