每日一题 - 最长子串

#include <vxWorks.h>

/* 字符的取值在ASCII范围内, 种类不超过128, 因此返回值类型使用UINT8即可 */
UINT8 lengthOfLongestSubstring(UINT8 *s)
    {
    /* 记录每个字符是否出现过. 种类不超过128, 因此使用2个UINT64即可 */
    UINT64 record[2] = {0};

    /* 子串边界. 因为字符串长度不超过50000, 因此使用UINT16即可 */
    UINT16 left = 0;
    UINT16 right = 0;

    /* 最长子串长度. 入参为空时, 子串长度为0 */
    UINT8 len = 0;

    if(s != 0)
        {
        while(s[right] != 0)
            {
            /* 如果右边界的字符已出现过, 例如X */
            while((record[s[right]>>6] & (1<<(s[right]&0x3f))) != 0)
                {
                /* 清除上次的X及X之前的字符状态 */
                record[s[left]>>6] &= ~(1<<(s[left]&0x3f));

                /* 移动左边界到上次的X之后 */
                left++;
                }

            /* 记录新字符的状态 */
            record[s[right]>>6] |= 1<<(s[right]&0x3f);

            /* 记录子串长度 */
            if((1+right-left)>len)
                {
                len = 1+right-left;
                }

            /* 移动右边界 */
            right++;
            }
        }
    return len;
    }