[Swift]LeetCode395. 至少有K个重复字符的最长子串 | Longest Su
发布时间:2020-12-14 05:05:28 所属栏目:百科 来源:网络整理
导读: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 = 3Output:3The longest substring is "aaa",a
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,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,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 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |