首页 > Windows开发 > 详细

LeetCode 395. Longest Substring with At Least K Repeating Characters C#

时间:2017-01-14 07:26:41      阅读:222      评论:0      收藏:0      [点我收藏+]

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#

原文:http://www.cnblogs.com/MiaBlog/p/6284432.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!