• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode395.至少有K个重复字符的最长子串|LongestSubstringwithAtLeastKRepea ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10303512.html
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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 。输出 的长度。

示例 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
iOS开发Swift开发数独游戏(二)数独题目的生成发布时间:2022-07-13
下一篇:
iOSSwift3.0OC数据储存--归档发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap