Monday, September 12, 2016

Leetcode 395 Longest Substring with At Least K Repeating Character Solution

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;
    }
};

No comments:

Post a Comment