首页 > 代码库 > LeetCode 395. Longest Substring with At Least K Repeating Characters C#
LeetCode 395. Longest Substring with At Least K Repeating Characters C#
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.
Solution:
Map all characters in string s to a Hash map and store the count of characters as values.
if all characters occur more than k times, then return the whole string length as result;
if not, find the least occured character and split the string by this char, then call this function recursively
to get the max length out of all substrings.
return the max.
1 public class Solution { 2 public int LongestSubstring(string s, int k) { 3 Dictionary<char,int> map = new Dictionary<char, int>(); 4 if(string.IsNullOrEmpty(s)) 5 { 6 return 0; 7 } 8 int l = s.Length; 9 for(int i=0; i<l; i++) 10 { 11 if(map.ContainsKey(s[i])) 12 { 13 map[s[i]]++; 14 } 15 else 16 { 17 map.Add(s[i],1); 18 } 19 } 20 char minKey=map.Aggregate((p, r) => p.Value < r.Value ? p : r).Key; 21 if(map[minKey]>=k) 22 { 23 return l; 24 } 25 string[] splitted = s.Split(minKey); 26 int max = 0; 27 foreach(string n in splitted) 28 { 29 int m = LongestSubstring(n,k); 30 if(m>max) 31 { 32 max = m; 33 } 34 } 35 return max; 36 37 } 38 }
LeetCode 395. Longest Substring with At Least K Repeating Characters C#
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。