class Solution { public: int lengthOfLongestSubstring(string s) { int len = s.length(); if (len < 2) return len; char cnt[256]; memset(cnt, 0, sizeof(cnt)); const char* p = s.c_str(); const char* q = p + 1; const char* end = s.c_str() + len - 1; int mlen = 1; cnt[*p] = 1; while(q <= end) { char ch = *q; int clen = q - p + (ch == 0); if (cnt[ch]) { // the character ch already exist in substr[p,q] for(; *p != ch; p++) cnt[*p] = 0; p++; } else { cnt[ch] = 1; } if (clen > mlen) mlen = clen; q++; } return mlen; } };
用[p, q]表示一个子串,cnt[ch]表示在这个子串中字符ch出现的次数,如果q移动到一个新的位置发现该位置上的字符ch对应的cnt[ch]==1,说明字符ch已经在[p, q-1]的子串中出现过,那么符合要求的子串必然不会包括[p, q]因为已经有重复了,那么我们就要让移动到子串中与ch重复的那个字符后面的位置如r(移动的同时要把经过的字符对应的计数清零),那么[r, q]子串中就没有重复了,就又可以继续向后检测了。
LeetCode Longest Substring Without Repeating Characters,布布扣,bubuko.com
LeetCode Longest Substring Without Repeating Characters
原文:http://www.cnblogs.com/lailailai/p/3601875.html