[Swift]LeetCode395. 至少有K个重复字符的最长子串 | Longest Substring with At Least K Repeating Characters
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10303512.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:
Input: s = "aaabb", k = 3 Output: 3 The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
Input: s = "ababbc", k = 2 Output: 5 The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
示例 1:
输入: s = "aaabb", k = 3 输出: 3 最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2:
输入: s = "ababbc", k = 2 输出: 5 最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
16ms
1 class Solution {
2 func longestSubstring(_ s: String, _ k: Int) -> Int {
3 guard s.count > 0 else {
4 return 0
5 }
6
7 guard k > 0 else {
8 return s.count
9 }
10
11 var result = Int.min
12 var sArray = s.map{ String($0) }
13
14 func splitString(string: [String]) {
15 guard string.count > 0 else {
16 return
17 }
18 var memo = [String: Int]()
19 var invalidChar = [String]()
20 for i in 0..<string.count {
21 memo[string[i]] = memo[string[i], default:0] + 1
22 }
23
24 var candidates = [[String]]()
25 var last = -1
26 var i = 0
27 while i < string.count {
28 if memo[string[i]]! < k {
29 if i <= last + 1 {
30 last = i
31 i += 1
32 continue
33 } else {
34 candidates.append(Array(string[last + 1..<i]))
35 last = i
36 }
37 }
38 i += 1
39 }
40
41 if last < string.count - 1{
42 candidates.append(Array(string[last + 1..<string.count]))
43 }
44
45 if last == -1 {
46 result = max(string.count, result)
47 return
48 }
49
50 for c in candidates {
51 splitString(string:c)
52 }
53 }
54
55 splitString(string:sArray)
56 return result == Int.min ? 0 : result
57 }
58 }20ms
1 class Solution {
2 func longestSubstring(_ s: String, _ k: Int) -> Int {
3 return helper(Array(s), 0, s.count, k)
4 }
5
6 func helper(_ s: [Character], _ left: Int, _ right: Int, _ k: Int) -> Int {
7 guard right - left >= k else { return 0 }
8 var counts = [Character: Int]()
9 for char in s[left..<right] {
10 counts[char] = (counts[char] ?? 0) + 1
11 }
12
13 for i in left..<right where counts[s[i]]! < k {
14 var j = i + 1
15 while j < right && counts[s[j]]! < k { j += 1 }
16 return max(helper(s, left, i, k), helper(s, j, right, k))
17 }
18 return right - left
19 }
20 }52ms
1 class Solution {
2 func longestSubstring(_ s: String, _ k: Int) -> Int {
3 var arr = Array(s)
4 var cmap:[Character:Int] = [:]
5
6 if s.length == 0 {
7 return 0
8 }
9
10 for c in arr {
11 if cmap[c] == nil {
12 cmap[c] = 0
13 }
14 cmap[c] = cmap[c]! + 1
15 }
16
17 var leastfreq = arr.count+1
18 var leastfreqchar:Character? = nil
19 for (letter, count) in cmap {
20 if count < leastfreq {
21 leastfreq = count
22 leastfreqchar = letter
23 }
24 }
25
26 if leastfreq >= k {
27 return s.count
28 }
29
30 var begin = 0
31 var maxsofar = 0
32 for i in 0...arr.count {
33 if i == arr.count || arr[i] == leastfreqchar {
34 let tmp = Array(arr[begin..<i])
35 let tmps:String = String(tmp)
36 maxsofar = max(maxsofar, longestSubstring(tmps, k))
37 begin = i+1
38 }
39 }
40
41 return maxsofar
42 }
43 }56ms
1 class Solution {
2 func longestSubstring(_ s: String, _ k: Int) -> Int {
3 if k <= 1 { return s.count }
4
5 let array = [Character](s)
6 var dict = [Character: Int]()
7 for c in array {
8 if let count = dict[c] {
9 dict[c] = count + 1
10 } else {
11 dict[c] = 1
12 }
13 }
14
15 var result = 0
16 var separator: Character? = nil
17 for key in dict.keys {
18 if let count = dict[key], count < k {
19 separator = key
20 break
21 }
22 }
23 if let separator = separator {
24 let subStringArray = s.components(separatedBy: String(separator))
25 for subString in subStringArray {
26 let temp = longestSubstring(subString, k)
27 if temp > result {
28 result = temp
29 }
30 }
31 } else {
32 return s.count
33 }
34 return result
35 }
36 }764ms
1 class Solution {
2 func longestSubstring(_ s: String, _ k: Int) -> Int {
3 if s.count < k {
4 return 0
5 }
6 var dict = [Character: Int]()
7 var i = 0
8 var j = 0
9 let ss = Array(s)
10 var maxLength = 0
11 for k in s {
12 dict[k] = (dict[k] ?? 0) + 1
13 }
14 let dict2 = dict.filter{$0.value < k}
15 if dict2.count == 0 {
16 return s.count
17 }
18 while j < s.count {
19 if let d = dict2[ss[j]] {
20 if d < k {
21 let start = s.index(s.startIndex, offsetBy: i)
22 let end = s.index(s.startIndex, offsetBy: j)
23 let range = start..<end
24 let subS = s[range]
25 maxLength = max(maxLength, longestSubstring(String(subS), k))
26 i = j + 1
27 }
28 }
29 j += 1
30 }
31 let start = s.index(s.startIndex, offsetBy: i)
32 let end = s.index(s.startIndex, offsetBy: j)
33 let range = start..<end
34 let subS = s[range]
35 maxLength = max(maxLength, longestSubstring(String(subS), k))
36 return maxLength
37 }
38 }948ms
1 class Solution {
2 func longestSubstring(_ s: String, _ k: Int) -> Int {
3 var n:Int = s.count
4 var max_idx:Int = 0
5 var res:Int = 0
6 var m:[Int] = [Int](repeating:0,count: 128)
7 var ok:Bool = true
8 for c in s.characters
9 {
10 m[c.ascii] += 1
11 }
12 for i in 0..<n
13 {
14 if m[s[i].ascii] < k
15 {
16 res = max(res, longestSubstring(s.subString(max_idx, i - max_idx), k))
17 ok = false
18 max_idx = i + 1
19 }
20 }
21 return ok ? n : max(res, longestSubstring(s.subString(max_idx, n - max_idx), k))
22 }
23 }
24
25 extension String {
26 //subscript函数可以检索数组中的值
27 //直接按照索引方式截取指定索引的字符
28 subscript (_ i: Int) -> Character {
29 //读取字符
30 get {return self[index(startIndex, offsetBy: i)]}
31 }
32
33 // 截取字符串：指定索引和字符数
34 // - begin: 开始截取处索引
35 // - count: 截取的字符数量
36 func subString(_ begin:Int,_ count:Int) -> String {
37 let start = self.index(self.startIndex, offsetBy: max(0, begin))
38 let end = self.index(self.startIndex, offsetBy: min(self.count, begin + count))
39 return String(self[start..<end])
40 }
41 }
42
43 //Character扩展方法
44 extension Character
45 {
46 //属性：ASCII整数值(定义小写为整数值)
47 var ascii: Int {
48 get {
49 let s = String(self).unicodeScalars
50 return Int(s[s.startIndex].value)
51 }
52 }
53 }- 上一篇 »PHP算法之无重复字符的最长子串
- 下一篇 »python经典算法题：无重复字符的最长子串