[LeetCode] 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.

問題描述：給定一個字符串，找到這個字符串中沒有重復字符的最長子串的長度。比如，給定字符串abcabcbb，最長的不重復的字符串就是abc，長度為3，給定字符串為bbbbb，只有一個字符b，長度為1。

最簡單的想法就是，找到所有的沒有重復字符的子串，得到最大的長度。用一個hash表存儲當前正在判斷的字符串的不重復的字符，用兩個迭代器得到一個區間，當第二個迭代器的字符不在hash表中，說明該字符是不重復的字符，那麼就遞增第二個迭代器，並將該字符加入到hash表中，否則，就獲取hash表的長度，這就是當前的不重復字符串的長度，與已經得到的最長的長度進行比較，然後清空hash表，遞增第一個迭代器，並將第二個迭代器置為第一個迭代器。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty())
			return 0;

		set hash;
		unsigned long n = 0;
		string::iterator start = s.begin();
		string::iterator iter = s.begin();

		while(start != s.end()) {
			if(iter != s.end() && hash.find(*iter) == hash.end()) {
				hash.insert(*iter);
				++iter;
			}
			else {
				if(hash.size() > n) {
					n = hash.size();
				}
				if(iter == s.end())
				    break;
				hash.clear();
				++start;
				iter = start;
			}
		}
		return n;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty())
			return 0;

		unsigned long n = 0;
		string::iterator start = s.begin();
		string::iterator iter = s.begin(), find_iter;

		while(start != s.end()) {
			if(iter != s.end() && (find_iter = find(start, iter, *iter)) == iter) {
				++iter;
			}
			else {
				if(iter - start > n) {
					n = iter - start;
				}
				if(iter == s.end())
					break;
				start = find_iter + 1;
				iter = start;
			}
		}
		return n;
    }
};