C++ simple solution


  • 0
    class Solution {
    public:
        int longestSubstring(string s, int k) {
            if (s.empty())
                return 0;
            int res = 0, n = s.size(), l = 0;
            int mp[26] = {0};
    
            for (auto i : s)
                mp[i - 'a']++;
                
            // check s is the longestSubstring
            bool f = false;
            for (auto i : mp)
                if (i < k && i > 0)
                    f = true;
            if (!f)
                return s.size();
                
            for (int i = 0; i < n; i++) {
                if (mp[s[i] - 'a'] < k) {
                    res = max(res, longestSubstring(s.substr(l, i - l), k));
                    l = i + 1;
                }
            }
            res = max(res, longestSubstring(s.substr(l), k));
            return res;
        }
    };
    
    

  • 0
    A

    @yong.cao.7731 said in C++ traverse solution not recursive:

        for (int i = 0; i < n; i++) {
            if (mp[s[i] - 'a'] < k) {
                res = max(res, longestSubstring(s.substr(l, i - l), k));
                l = i + 1;
            }
        }
        res = max(res, longestSubstring(s.substr(l), k));
    

    This is totally recursive.


  • 0

    @ayuanx
    Oh, you are right. I will change the title.
    sorry for the that.
    Why i thought it was recursive??? I have no ideal.....


Log in to reply
 

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