Problem: Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k. It is given that input string can only have lowercase English letters.
Example:
Input: s = "aaabbbccddd", k = 3 Output: 6 Explanation: The longest substring is "aaabbb", as 'a' and 'b' are repeated 3 times.
Approach: We can use two pointers approach here. First we find the number of unique characters in the input string. Now the approach here is to look for unique characters of a certain number (increasing by 1 each time you loop from 1 to number of unique characters) and update the result when each of these unique characters has at least count K.
That's all!
Implementation in C#:
public int LongestSubstring(string s, int k)
{
int totalUniqueCharacters = this.GetUniqueCharacters(s);
int maxLen = 0;
for (int unique = 1; unique <= totalUniqueCharacters; ++unique)
{
int currUnique = 0, charWithAtLeastCountK = 0, windowStart = 0, windowEnd = 0;
int[] frequencyMap = new int[26];
while(windowEnd < s.Length)
{
if (currUnique <= unique)
{
int currIndex = s[windowEnd] - 'a';
if (frequencyMap[currIndex] == 0)
{
++currUnique;
}
++frequencyMap[currIndex];
if (frequencyMap[currIndex] == k)
{
++charWithAtLeastCountK;
}
++windowEnd;
}
else
{
int currIndex = s[windowStart] - 'a';
if (frequencyMap[currIndex] == k)
{
--charWithAtLeastCountK;
}
if (frequencyMap[currIndex] > 0)
{
--frequencyMap[currIndex];
if (frequencyMap[currIndex] == 0)
{
--currUnique;
}
}
++windowStart;
}
if (currUnique == unique && currUnique == charWithAtLeastCountK)
{
maxLen = Math.Max(maxLen, windowEnd - windowStart);
}
}
}
return maxLen;
}
private int GetUniqueCharacters(string s)
{
bool[] charHash = new bool[26];
int countUniqueChars = 0;
foreach(char ch in s)
{
if (charHash[ch - 'a'] == false)
{
++countUniqueChars;
charHash[ch - 'a'] = true;
}
}
return countUniqueChars;
}
Complexity: O(total unique characters * n) = O(26 * n) = O(n)
No comments:
Post a Comment