LeetCode #003 Longest Substring Without Repeating Characters，

003 Longest Substring Without Repeating Characters

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.

Input: abcabccbb
Output: 3
题意：找到一个字符串中，没有重复字符的最长子串，返回它的长度

思路：

a	b	c	d	a

0	1	2	3	5

代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int Max=0;
        int LastPosition=0;
        int HashTable[255]={-1};
        int i=0;
        for(i=0;i<s.size();i++){
            int temp=(int)s[i];
            if(HashTable[temp]>0){
                LastPosition=std::max(LastPosition,HashTable[temp]);
            }
            HashTable[temp]=i+1;
            Max=std::max(Max,HashTable[temp]-LastPosition);
        }
        return Max;
    }
};

知识点

In my understanding, the dynamic programming is: every decision depends on the current status, and immediately cause the transfer of status. In this problem, flag is the status, and we can get the longest every time depends on the previous longest and the flag, so I think it also can be seen as DP solution, even though not obvious compared to the Maximum Subarray problem.

class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        std::vector<int> flag(256, -1);
        int start = 0, longest = 0, len = s.size();
        for (int i = 0; i != len; ++i) {
            if (flag[s[i]] >= start) {
                longest = std::max(longest, i - start);
                start = flag[s[i]] + 1;
            }
            flag[s[i]] = i;
        }
        return std::max(longest, len - start);
    }
};