最大连续子串的长度-动态规划

描述

字符串的最大连续子串的长度，子串不能有重复字符,例如
输入："abcabcbb"
输出：3

输入："bbbbb"
输出：1

输入："pwwkew"
输出：3

思路

使用动态规划来解决问题，先找到状态转移方程

• n表示源字符串的下标
• sum(n)表示以n为结尾的字符串的最大不重复子串的长度
• m(n)表示下标为n对应的字符，并且以该字符为结尾的最大连续子串
• 如果n出现在m(n-1)，sum(n) = n - f(n),f(n)表示n出现在m(n-1)中对应的下标
• 如果n没有出现在m(n-1),sum(n) = sum(n-1) + 1
• 令max(n)表示最终结果，max(n) = max(sum(n),sum(n-1)...sum(0))

Code

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        if s.count == 0 {
            return 0
        }
        
        var sum = 0
        var maxSum = 0
        var dic:[Character:Int] = [:]
        var i = 0
        var j = 0
        for c in s {
            if dic[c] == nil {
                sum = sum + 1
            } else {
                let val = dic[c]!
                if val >= j {
                    sum = i - val
                    j = val + 1
                } else {
                    sum = sum + 1
                }
            }
            dic[c] = i
            i = i+1
            maxSum = max(maxSum, sum)
        }
        return maxSum
    }
}

代码分析

时间复杂度O(n)

• 把遍历过的字符存储到字典里面，key为字符，value为字符对应的下标,采用字典的数据结构是因为，字典的存取都为O(1)
• 定义变量 j 标记上一个最大连续子串的开始下标，用来做状态转移