LeetCode - #159 至多包含两个不同字符的最长子串（会员题）

原创

Swift社区

发布于 2024-12-28 23:08:51

1680

文章被收录于专栏：Swift社区Swift社区

前言

本题为 LeetCode 的高级会员解锁题

我们社区陆续会将顾毅（Netflix 增长黑客，《iOS 面试之道》作者，ACE 职业健身教练。）的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新到 156 期，我们会保持更新时间和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，我们希望大家可以在上班路上阅读，长久积累会有很大提升。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

1. 描述

给定一个字符串 s ，找出至多包含两个不同字符的最长子串 t ，并返回该子串的长度。

2. 示例

示例 1

输入: "eceba"
输出: 3
解释: t 是 "ece"，长度为3。

示例 2

输入: "ccaabbb"
输出: 5
解释: t 是 "aabbb"，长度为5。

约束条件：

1 <= s.length <= 10^5
s 由英文字母组成

3. 答案

class LongestSubstringMostTwoDistinctCharacters {
    func lengthOfLongestSubstringTwoDistinct(_ s: String) -> Int {
        var start = 0, longest = 0, charFreq = [Character: Int]()
        let sChars = Array(s)
        
        for (i, char) in sChars.enumerated() {
            if let freq = charFreq[char] {
                charFreq[char] = freq + 1
            } else {
               if charFreq.count == 2 {
                    longest = max(longest, i - start)
                    
                    while charFreq.count == 2 {
                        let charStart = sChars[start]
                        charFreq[charStart]! -= 1
                        
                        if charFreq[charStart] == 0 {
                            charFreq[charStart] = nil
                        }
                        
                        start += 1
                    }   
                }
                
                charFreq[char] = 1
            }
        }
        
        return max(longest, sChars.count - start)
    }
}