3_无重复字符的最长子串

【问题描述】

给定一个字符串 s ，请你找出其中不含有重复字符最长子串的长度。

示例:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

【算法设计思想】

此题为典型的滑动窗口问题，这类问题的主要是处理数组或者字符串的子数组或者子字符串问题。滑动窗口算法通过一个动态变化的窗口来解决此类问题。

在这里我将这个问题大体分为以下两类：

1.寻找最长：
步骤一：左右指针（L,R)在起始点，R向右逐位滑动，并更新结果。
步骤二：在每次滑动过程中，如果窗内的元素满足条件，则继续向右滑动，如果不满足条件，则删除左边的元素（即右移左指针）以此来缩小窗口。
步骤三：直到R到达最右端。

2.寻找最短：
步骤一：左右指针（L,R)在起始点，R向右逐位滑动，并更新结果。
步骤二：在每次滑动过程中，如果窗内的元素满足条件，则L向右滑动更新结果，如果不满足条件，则R向右扩大窗口。
步骤三：直到R到达最右端。

在本题的具体解法，则是先初始化一个名为occ的集合，然后用变量n来记录下当前字符串s的长度，记录右指针为rk，ans即为answer的缩写，作为本题所返回的变量。
先写一个for循环，其中循环变量i为左指针，从0到n，然后判断下i的值。while循环主要是看s[rk+1]（即rk这个右指针所指向的下一个字符）是不是在occ这个集合中，如果在这个集合中那么就跳出循环，如果不在这个集合中进入循环，加入此字符到occ集合内，然后rk++。
最后返回ans，注意这里在每一次外层循环结束之后会更新ans，即比较ans和occ中字符串的大小，取较大的那个数。

【算法描述】

Python:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        occ = set()
        n = len(s)
        rk = -1
        ans = 0
        for i in range(n):
            if(i != 0):
                occ.remove(s[i-1])
            while rk + 1 < n and s[rk+1] not in occ:
                occ.add(s[rk+1])
                rk = rk + 1
            ans = max(ans,rk-i+1)
        return ans

Java:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        int rk = -1;
        int ans = 0;
        for(int i = 0; i < n; ++i){
            if(i != 0){
                occ.remove(s.charAt(i-1));
            }
            while(rk + 1 < n && !occ.contains(s.charAt(rk+1))){
                occ.add(s.charAt(rk+1));
                ++rk;
            }
            ans = Math.max(ans,rk-i+1);
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int rk = -1;
        int ans = 0;
        unordered_set<char> occ;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                occ.erase(s[i - 1]);
            }
            while(rk + 1 < n && !occ.count(s[rk+1])){
                occ.insert(s[rk + 1]);
                ++rk;
            }

            ans = max(ans,rk-i+1);
        }
        return ans;
    }
};

C语言：

int lengthOfLongestSubstring(char* s) {
    int left = 0;
    int right = 0;
    int max = 0;
    int i, j;
    int len = strlen(s);
    int haveSameChar = 0;
    for (i = 0; i < len; ++i) {
        if (left <= right) {
            haveSameChar = 0;
            for (j = left; j < right; j++) {
                if (s[j] == s[right]) {
                    haveSameChar = 1;
                    break;
                }
            }

            if (haveSameChar) {
                left = j + 1;
            }
        }
        max = (max < (right - left + 1)) ? (right - left + 1) : (max);
        right++;
    }
    return max;
}

l