3.无重复字符的最大字串

无重复字符的最大子串

暴力遍历

暴力的思路还是非常简单的，一个n^2的暴力循环。第一个循环是第一位是哪一位，第二个循环是后面满足条件的最大位数。
第一反应没能写出来是因为没有想到set。对于稍微有些特别的数据结构并不是特别敏感。

def lengthOfLongestSubstring(s: str) -> int:
    n = len(s)
    max_length = 0
    
    # 遍历每个可能的起始位置
    for i in range(n):
        # 使用集合来跟踪已经出现的字符
        char_set = set()
        current_length = 0
        
        # 从起始位置向后扩展
        for j in range(i, n):
            # 如果当前字符已经在集合中，表示遇到了重复字符
            if s[j] in char_set:
                break
            
            # 将当前字符添加到集合中，并增加当前子串长度
            char_set.add(s[j])
            current_length += 1
        
        # 更新最大长度
        max_length = max(max_length, current_length)
    
    return max_length

但是对于C++而言，这里又要用到stl标准库中的unordered_set<>容器。回想我当时学习C++的时候，几乎就没有怎么用过这些stl容器。。但是对于这种题目使用这种容器几乎是唯一解法，因为不使用stl会使其极度复杂，因为你需要自己定义这种结构体。
所以现在学习算法的时候我会顺带学习一下C++的常用stl。
https://www.runoob.com/cplusplus/cpp-libs-unordered_set.html

#include <string>
#include <unordered_set>
#include <algorithm>

class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        int n = s.length();
        int maxLength = 0;
        
        // 遍历每个可能的起始位置
        for (int i = 0; i < n; i++) {
            // 使用unordered_set来跟踪已经出现的字符
            std::unordered_set<char> charSet;
            int currentLength = 0;
            
            // 从起始位置向后扩展
            for (int j = i; j < n; j++) {
                // 如果当前字符已经在集合中，表示遇到了重复字符
                if (charSet.find(s[j]) != charSet.end()) {
                    break;
                }
                
                // 将当前字符添加到集合中，并增加当前子串长度
                charSet.insert(s[j]);
                currentLength++;
            }
            
            // 更新最大长度
            maxLength = std::max(maxLength, currentLength);
        }
        
        return maxLength;
    }
};

滑动窗口

理解成一个小窗口在移动，一直划选着符合条件的内容。
窗口初始化为0，将第一个元素添加进窗口，随后检测第二个元素是否存在于窗口：
如果不存在则添加进窗口。如果存在则循环删除窗口内最左侧元素直到满足条件。
满足条件后记录目前的长度并和最大长度进行比较。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len

作者：powcai
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/3982/hua-dong-chuang-kou-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。  

---

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        unordered_set<char> lookup;
        int maxStr = 0;
        int left = 0;
        for(int i = 0; i < s.size(); i++){
            while (lookup.find(s[i]) != lookup.end()){
                lookup.erase(s[left]);
                left ++;
            }
            maxStr = max(maxStr,i-left+1);
            lookup.insert(s[i]);
    }
        return maxStr;
        
    }
};

作者：powcai
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/3982/hua-dong-chuang-kou-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度分析：
乍一看，这段代码似乎有嵌套循环（外部for循环和内部while循环），可能让人觉得时间复杂度是O(n²)。但实际上，这个算法的总体时间复杂度是O(n)，其中n是字符串的长度。
原因如下：

外部的for循环明确执行n次，每次处理字符串中的一个字符。
关键在于内部的while循环：虽然它看起来可能在最坏情况下对每个字符都执行多次，但实际上，字符串中的每个字符最多只会被处理两次:

一次是在外部for循环中被添加到窗口（lookup集合）
一次是在while循环中被移出窗口

左指针left在整个过程中最多移动n次（从0到n-1）。
每次执行while循环体，left指针都会向右移动一位。所以while循环体的总执行次数不会超过n次。

所以，虽然代码中有嵌套的循环结构，但内部while循环的总执行次数受到字符串长度n的限制，使得整体时间复杂度仍然是O(n)。
详细解释为什么while循环总执行次数不超过n：

每次执行while循环，left指针都会向右移动一位
left指针在整个算法执行过程中只会从0移动到最多n-1
因此，while循环的总执行次数不能超过n

空间复杂度：
空间复杂度是O(min(m, n))，其中m是字符集的大小，n是字符串长度。因为在最坏情况下，lookup集合最多包含min(m, n)个字符。
这就是为什么滑动窗口是解决这类问题的高效方法，它避免了暴力解法中的重复计算，将时间复杂度从O(n²)降低到O(n)。

此外，insert方法和erase方法分别是添加和删除。