LeetCode 395 至少有K个重复字符的最长子串 [Swift]
2019-08-13
题目
找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
示例 1:
输入: s = “aaabb”, k = 3
输出: 3
最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。
示例 2:
输入: s = “ababbc”, k = 2
输出: 5
最长子串为 “ababb” ，其中 ‘a’ 重复了 2 次， ‘b’ 重复了 3 次。
思路
如果某个字符 x 在整个字符串中出现的次数 < k，那么 x 不可能出现在最终要求的子串中。因此，可以将原字符串截断为：x 左侧字符子串 + x + x 右侧字符子串。因此，问题就被拆分为对左子串、右子串求解这两个子问题。下面的代码采用递归求解：
class Solution {
func longestSubstring(_ s: String, _ k: Int) -> Int {
return find(s, k, 0, s.count - 1);
}
func find(_ s: String, _ k: Int, _ left: Int, _ right: Int) -> Int {
if left > right {
return 0
}
var charDict = [Character : [Int]]()
var index = 0;
for c in s.subString(left, right - left + 1) {
if charDict[c] == nil {
charDict[c] = []
}
charDict[c]!.append(left + index)
index += 1
}
for c in charDict.keys {
let count = charDict[c]!.count;
if count > 0 && count < k {
let pos = charDict[c]![0]
return max(find(s, k, left, pos - 1), find(s, k, pos + 1, right))
}
}
return right - left + 1;
}
}
extension String {
func subString(_ start : Int, _ length : Int = -1) -> String {
var len = length
if len == -1 {
len = self.count - start
}
let st = self.index(startIndex, offsetBy:start)
let en = self.index(st, offsetBy:len)
return String(self[st ..< en])
}
}