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.

點選這個連結你可以看到更多的解決方法：https://oj.leetcode.com/discuss/6168/my-o-n-solution

下面是我自己的方法，線上AC通過。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int max = 0;
        
        // 記錄子串起始位置的前一個位置的下标
        // 初始化為-1
        int idx = -1;
        
        // 記錄字元在s中出現的位置
        int locs[256];
        memset(locs, -1, sizeof(int) * 256);
        for (int i = 0; i < s.size(); i++) {
            // 如果s[i]在目前子串中出現過
            if (locs[s[i]] > idx) {
                // 新子串的起始位置設為s[i]出現的位置+1
                // P.S. idx是記錄起始位置的前一個位置的下标
                idx = locs[s[i]];
            }
            // 如果目前子串的長度大于最大值
            if (i - idx > max) {
                max = i - idx;
            }
            // 更新字元s[i]出現的位置
            locs[s[i]] = i;
        }
        return max;
    }
};