Leetcode3: Longest Substring Without Repeating Characters

Leetcode 3: 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.

大意： 找到一个字符串里面最长无重复字母的子字符串

分析： 有两种做法，一种是用map, 一种是用set
M1: use map
       key: char value: index of that char
       需要一个start指针，表示当前最长子串的起始位置。
      如果char 不在map 中， 将该char 放进map, 并且同时更新最长子串
      如果char  在map 中， 我们需要删除从 start 到该char 的所有字符，使得这个字符在map中没有重复。首先获取该char 之前在map 中的index, 将所有的value = 0； 并且将新char的位置更新，然后update start 的位置。
 worst case : time complexity is O(n), 最多扫描两遍string
M2: use set
      keep a start pointer and an end pointer
     if end char is not in the set, insert the end char into set and do end++ to explore the next char, update the max_length of the substring; if end char is in the set, erase the start char and do start++ until the end char is erased;
     time complexity is O(nlogn), as the time complexity of insert and erase operation in set is both log(n), but the code is shorter and the space complexity is less than using map.
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //sanity check
        if (s.size() == 0) return 0;
        //use a set to store unduplicate chars
        set<int> se;
        int max_len = 0;
        int left = 0;
        int right = 0;
        for (;right < s.size(); right++) {
            if (se.find(s[right]) == se.end()) { //case 1: char not in set
                se.insert(s[right]);
                //update max_len
                max_len = max(max_len, right-left+1);
            }else { //case2: char in set
                se.erase(s[left++]);
                right--;
            }
        }
        return max_len;
    }
};

updated:
 不需要用map/set，对于以char为key 的 map， 可以直接用一个size 为256的一维数组来存储，数组的index是key， value是该字符在string里的位置。 这样就节省了空间。
用下面的方法，对sliding window进行了特殊的处理方式，只需要扫描一遍string，节省了时间。
判断存在duplicate的条件，不再是看map或者set里面有没有这个元素，而是看当前元素的value是不是比窗口左边大，如果大，说明当前元素已经在array中，找到了一个duplicate；如果小，说明当前元素是在窗口左边之外，是已经无用的元素，需要更新其index值。  

class Solution {
public:
//sliding window
    int lengthOfLongestSubstring(string s) {
        //sanity check
        if (s.size() == 0) return 0;
        int left = 0;
        int right = 1;
        int carray[256];
        for (int i = 0; i < 256; i++) {
            carray[i] = -1;
        }
        int maxl = 1;
        carray[s[0]] = 0;
        for (; right < s.size(); right++) {
            if (carray[s[right]] >= left) {
                left = carray[s[right]] + 1;
            }
            maxl = max(maxl, right- left + 1);
            carray[s[right]] = right;
        }
        return maxl;
    }
};

updated:
最精简的写法了！

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0) return 0;
        //unordered_set<char> iset;
        int iset[256] = {0};
        int left = 0;
        int right = 0;
        int gmax = 0;
        while (right < s.size()) {
          if (iset[s[right]] > 0) {
              iset[s[left]]--;
              left++;
          } else {
              iset[s[right]]++;
              right++;
          }
          gmax = max(gmax, right-left);
        }
        return gmax;
    }
};