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

【分析】

从左到右扫描，当遇到重复字母时，以上一个重复字母的index+1，作为新的搜索起始位置，直到最后一个字母。

【代码】

/*********************************
*   日期：2015-01-20
*   作者：SJF0115
*   题目: 3.Longest Substring Without Repeating Characters
*   网址：https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/
*   结果：AC
*   来源：LeetCode
*   时间复杂度：O(n)
*   空间复杂度：O(1)
*   博客：
**********************************/
#include <iostream>
#include <cstring>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        if(len <= 1){
            return len;
        }//if
        bool visited[256];
        // 初始化
        memset(visited,false,sizeof(visited));
        // 计算
        int max = 0,cur = 0,start = 0;
        for(int i = 0;i < len;){
            // 没有元素和该元素重复
            if(!visited[s[i]]){
                visited[s[i]] = true;
                ++cur;
                ++i;
            }//if
            else{
                // 更新最大长度
                if(cur >= max){
                    max = cur;
                }//if
                cur = 0;
                memset(visited,false,sizeof(visited));
                int index = 0;
                // 寻找之前重复元素的下一个元素的下标
                for(int j = start;j < i;++j){
                    if(s[i] == s[j]){
                        index = j+1;
                        break;
                    }//if
                }//for
                start = index;
                i = index;
            }
        }//for
        if(cur > max){
            max = cur;
        }//if
        return max;
    }
};

int main(){
    Solution solution;
    string str("abbacdafg");
    int result = solution.lengthOfLongestSubstring(str);
    // 输出
    cout<<result<<endl;
    return 0;
}

【代码二】

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        if(len <= 1){
            return len;
        }//if
        // 记录上次出现的位置
        int last[256];
        // 初始化
        memset(last,-1,sizeof(last));
        // 计算
        int max = 0,cur = 0,start = 0;
        for(int i = 0;i < len;++i){
            // 有元素和该元素重复
            if(last[s[i]] >= 0){
                if(cur > max){
                    max =cur;
                }//if
                // 当遇到重复字母时，以上一个重复字母的index+1，
                // 作为新的搜索起始位置
                i = last[s[i]] + 1;
                cur = 0;
                memset(last,-1,sizeof(last));
            }//if
            ++cur;
            last[s[i]] = i;
        }//for
        if(cur > max){
            max = cur;
        }//if
        return max;
    }
};

【分析三】

对上一个思路继续进行优化。

在上一个思路中当遇到重复字母时，以上一个重复字母的index+1，作为新的搜索起始位置。上一个重复字母的下一个字母到当前字母可以不用重复遍历。

在本思路中搜索起点不是上一个重复字母的index+1而是当前字母。

通过记录上一个Lonest Substring Without Repeating Characters的起点，来计算出在当前字母时的长度。

【代码三】

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        if(len <= 1){
            return len;
        }//if
        // 记录上次出现的位置
        int last[256];
        // 初始化
        memset(last,-1,sizeof(last));
        // 计算
        int max = 0,cur = 0,start = 0;
        for(int i = 0;i < len;++i){
            int pos = (int)s[i];
            // 有元素和该元素重复
            if(last[pos] >= start){// not last[pos] >= 0
                // 更新长度
                cur = cur - (last[pos] - start);
                // 更新起点
                start = last[pos] + 1;
            }//if
            else{
                ++cur;
            }
            // 更新字符位置
            last[pos] = i;
            if(cur > max){
                max =cur;
            }//if
        }//for
        return max;
    }
};