8 lines C++, O(n) 8ms


  • 12

    Solution 1 (array, 8ms)

    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int ctr[256] = {}, j = -1, distinct = 0, maxlen = 0;
        for (int i=0; i<s.size(); ++i) {
            distinct += ctr[s[i]]++ == 0;
            while (distinct > k)
                distinct -= --ctr[s[++j]] == 0;
            maxlen = max(maxlen, i - j);
        }
        return maxlen;
    }
    

    Solution 2 (unordered_map, 56ms)

    int lengthOfLongestSubstringKDistinct1(string s, int k) {
        unordered_map<char, int> ctr;
        int j = -1, maxlen = 0;
        for (int i=0; i<s.size(); ++i) {
            ++ctr[s[i]];
            while (ctr.size() > k)
                if (--ctr[s[++j]] == 0)
                    ctr.erase(s[j]);
            maxlen = max(maxlen, i - j);
        }
        return maxlen;
    }

  • 1

    @StefanPochmann do you have any Python trick in mind to solve this problem in fewer lines than 8?

    class Solution(object):
        def lengthOfLongestSubstringKDistinct(self, s, k):
           i, j, freqs, res = 0, 0, collections.defaultdict(int), 0
           for j in range(len(s)):
                freqs[s[j]] += 1
                if len(freqs) <= k: 
                    res = max(res, j - i + 1)
                while i <= j and len(freqs) > k:
                    freqs[s[i]] -= 1
                    if not freqs[s[i]]: 
                        freqs.pop(s[i], 0)
                    i += 1
            return res
    

  • 0

    @agave Not yet, no. Here's my old one, condensed like you probably counted yours it would also get exactly 8 lines:

    def lengthOfLongestSubstringKDistinct(self, s, k):
        j = -1
        maxlen = 0
        ctr = collections.Counter()
        for i, c in enumerate(s):
            ctr[c] += 1
            while len(ctr) > k:
                j += 1
                ctr[s[j]] -= 1
                if ctr[s[j]] == 0:
                    del ctr[s[j]]
            maxlen = max(maxlen, i - j)
        return maxlen

  • -1

    @agave Maybe I could get it down by doing silly stuff like emulating s[++j] with this:

    >>> j = [-1]
    >>> s = 'abc'
    >>> s[j.append(j.pop() + 1) or j[0]]
    'a'
    >>> s[j.append(j.pop() + 1) or j[0]]
    'b'
    >>> s[j.append(j.pop() + 1) or j[0]]
    'c'
    

  • 0

    @StefanPochmann still wonder why the hell Guido hasn't approved i++ and --i.


  • 1

    @agave Well, --i actually does exist, it just doesn't do what you want it to :-)

    When I started with Python and learned that it doesn't have those operations, I was appalled. But now I agree with this top-voted answer that it's rarely needed and when I do need it, I don't mind having to write a separate += or -= statement.


  • 0
    L

    How is this O(N) in time? Is it because k is assumed to be a constant? Why do I feel this should be O(N*k) due to the double loop?


  • 0

    @L0u1s No, k is part of the input, not a constant. The only thing I apparently (and apparently correctly) assumed about k is that it isn't negative. And then this is clearly O(n).


  • 0
    L

    @StefanPochmann thanks for the reply. Could you elaborate how is it "clearly" O(N)?

    From one aspect, by looking at the structure of the code, the nested loop looks like it's more than just O(N).

    But from another, I can also feel that the inner loop will not always run, or always run as a constant factor. So it feels like the inner loop is be a constant on average, or when amortized. But I cannot reason this in a better way. Could you elaborate on the time complexity being O(N)?


  • -1

    @L0u1s Yes, it's amortized O(1). Overall, the inner loop can't run more than n times. Think about how distinct and j evolve.


Log in to reply
 

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