C++ recursive


  • 0
    B

    the goal is to find a string with all char appear more than k times
    we first count all char in input string, if any char appear less than k times, we then split the input string according to the index of char less than k times, and recursively check the new string

    class Solution {
    public:
        int longestSubstring(string s, int k) {
            if(s.empty()) return 0;
            unordered_map<char, vector<int>>mp;
            for(int i = 0; i < s.length(); i++)
            {
                mp[s[i]].push_back(i);
            }
            vector<int>split;
            for(auto e : mp)
            {
                if(e.second.size() < k)
                    for(auto f : e.second) split.push_back(f);
            }
            if(split.empty()) return s.length();
            sort(split.begin(), split.end());
            int start = 0, ans = 0;
            for(auto e : split)
            {
                ans = max(ans, longestSubstring(s.substr(start, e-start), k));
                start = e+1;
            }
            return max(ans, longestSubstring(s.substr(start), k));
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.