一篇聊聊最长未重复子字符串

前言

我们社区从本期开始会将顾毅(Netflix 增长黑客，篇聊《iOS 面试之道》作者，聊最ACE 职业健身教练。长未串微博:@故胤道长[1])的重复字符 Swift 算法题题解整理为文字版以方便大家学习与阅读。

该算法题解的篇聊 github 仓库地址是：https://github.com/soapyigu/LeetCode-Swift[2]

不积跬步，无以至千里;不积小流，聊最无以成江海，长未串Swift社区 伴你前行。重复字符

1. 描述

给定一个字符串 s ，篇聊 找出最长未重复的服务器托管聊最子字符串的长度。

2. 示例

示例 1

输入：s = "abcabcbb" 输出：3 解释：最长未重复子字符串答案是长未串"abc"，长度为 3。重复字符 

示例 2

输入：s = "bbbbb" 输出：1 解释：最长未重复子字符串答案是篇聊"b"，长度为 1。聊最 

示例 3

输入：s = "pwwkew" 输出：1 解释：最长未重复子字符串答案是长未串"wke"，长度为 3。注意答案必须是高防服务器子字符串，“pwke” 是一个子列，而不是一个子字符串。 

示例 4

输入：s = "" 输出：0 

3. 答案

class LongestSubstringWithoutRepeatingCharacters {      func lengthOfLongestSubstring(_ s: String) -> Int {          var maxLen = 0, startIdx = 0, charToPos = [Character: Int]()         let sChars = Array(s)         for (i, char) in sChars.enumerated() {              if let pos = charToPos[char] {                  startIdx = max(startIdx, pos)             }             // update to next valid position             charToPos[char] = i + 1             maxLen = max(maxLen, i - startIdx + 1)         }         return maxLen     } } 

主要思想：使用字典存储非重复子字符串的下一个可能有效字符的位置,然后迭代字符串更新 maxLen、dictionary 和遇到重复时的 startIdx。

时间复杂度：O(n) 空间复杂度：O(n)