【LeetCode】字符串分类之无重复字符的最长子串

目录

题目

示例

解题思路

算法推演:

实现代码

复杂度分析

---

题目

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

 

示例

示例 1:输入: "abcabcbb"输出: 3解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。​示例 2:输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。​示例 4:输入: "dvdf"输出: 3

 

解题思路

设: 

• 滑动窗口，保证每个窗口里字母都是唯一的

• 使用 vector<int> m 来记录一个字母如果后面出现重复时，i 应该调整到的新位置所以每次更新的时候都会保存 j + 1 ，即字母后面的位置

•  j 表示子串的最后一个字母，计算子串长度为 j - i + 1

 

算法推演:

 

实现代码

class Solution {public:    int lengthOfLongestSubstring(std::string s) {        std::vector<int> m(128, 0);        int ans = 0;        int i = 0;        for (int j = 0; j < s.size(); j++) {            i = std::max(i, m[s[j]]);            m[s[j]] = j + 1;            ans = std::max(ans, j - i + 1);        }        return ans;    }};

 

复杂度分析

时间复杂度：O(N)，其中N是字符串的长度。

空间复杂度：O(1)