Problem Statement could be found @https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
Solution:-
Idea is to first count all character occurrence in a string. If a character is repeated less than k times, then is shouldn't be considered and can act string splitter.
class Solution {
int repeatCount;
int maxSubSize;
public:
int helper(string s){
int tempMaxSize = 0;
if (s.size() < repeatCount){
return 0;
}
//int tempMaxSize
int arr[26] = {0};
for (int i=0;i<s.size();i++){
arr[s.at(i) -'a'] ++;
}
int startLength = 0;
int flag = false;
int charCount = 0;
for (int i=startLength;i<s.size();i++){
// this could act as breaker
int charVal = (s.at(i) -'a');
if (arr[charVal] < repeatCount){
if (charCount == 0)
charCount = 1;
string temp = s.substr(startLength,charCount);
int tempL = helper(temp);
if (tempL > tempMaxSize)
tempMaxSize = tempL;
startLength = i+1;
flag = true;
charCount = 0;
}else{
charCount ++;
}
}
if (flag == false && s.size() >= repeatCount ){
//maxSubSize = s.size();
tempMaxSize = s.size();
return tempMaxSize ;
}else{
string temp = s.substr(startLength);
int tempL = helper(temp);
if (tempL > tempMaxSize){
tempMaxSize = tempL;
}
}
return tempMaxSize;
}
int longestSubstring(string s, int k) {
repeatCount = k ;
maxSubSize = 0;
int tempMaxSize = helper(s);
if (tempMaxSize > maxSubSize)
return tempMaxSize;
else
return maxSubSize;
}
};
Solution:-
Idea is to first count all character occurrence in a string. If a character is repeated less than k times, then is shouldn't be considered and can act string splitter.
class Solution {
int repeatCount;
int maxSubSize;
public:
int helper(string s){
int tempMaxSize = 0;
if (s.size() < repeatCount){
return 0;
}
//int tempMaxSize
int arr[26] = {0};
for (int i=0;i<s.size();i++){
arr[s.at(i) -'a'] ++;
}
int startLength = 0;
int flag = false;
int charCount = 0;
for (int i=startLength;i<s.size();i++){
// this could act as breaker
int charVal = (s.at(i) -'a');
if (arr[charVal] < repeatCount){
if (charCount == 0)
charCount = 1;
string temp = s.substr(startLength,charCount);
int tempL = helper(temp);
if (tempL > tempMaxSize)
tempMaxSize = tempL;
startLength = i+1;
flag = true;
charCount = 0;
}else{
charCount ++;
}
}
if (flag == false && s.size() >= repeatCount ){
//maxSubSize = s.size();
tempMaxSize = s.size();
return tempMaxSize ;
}else{
string temp = s.substr(startLength);
int tempL = helper(temp);
if (tempL > tempMaxSize){
tempMaxSize = tempL;
}
}
return tempMaxSize;
}
int longestSubstring(string s, int k) {
repeatCount = k ;
maxSubSize = 0;
int tempMaxSize = helper(s);
if (tempMaxSize > maxSubSize)
return tempMaxSize;
else
return maxSubSize;
}
};
No comments:
Post a Comment