7 lines C++


  • 17

    Based on the Python solution by @dalwise. Use a sliding window s[i:j], always add the new character, and remove the first window character if the extension isn't ok. So in each step, either extend the window by one or move it by one.

    int characterReplacement(string s, int k) {
        int i = 0, j = 0, ctr[91] = {};
        while (j < s.size()) {
            ctr[s[j++]]++;
            if (j-i - *max_element(ctr+65, ctr+91) > k)
                ctr[s[i++]]--;
        }
        return j - i;
    }

  • 0

    One suggestion is that you don't have to calculate max element by comparing all elements. You only care whether current updated one is longer than existed one, since shorter ones contribute nothing.


  • 0

    @clydexu I don't think that works, but maybe I just don't understand what you mean. Can you please show the code?


  • 1

    @StefanPochmann
    as long as max_same does not increase, you are able to maintain the current result.
    point is we are only looking for the longest one.

    int characterReplacement(string s, int k) {
            int size = s.size(), result = 0, start = 0, max_same = 0, count[256] = {0};
            for (int i = 0; i < size; i++)
                if ((max_same = max(++count[s[i]], max_same)) < i - start + 1 - k)
                    --count[s[start++]];
            return size - start;
        }
    

  • 0
    A

    @clydexu said in 7 lines C++:

        for (int i = 0; i < size; i++)
            if ((max_same = max(++count[s[i]], max_same)) < i - start + 1 - k)
                --count[s[start++]];
        return size - start;
    

    I think there are 2 bugs.

    1. max_same would never decrease.
    2. the substring does not necessarily end at size.

  • 0

    @ayuanx Show an input where it fails?


  • 0
    A

    @StefanPochmann I haven't tried any testcases. It's just my pure theory. I will try to fool around some tests.


  • 0
    A

    @StefanPochmann After some thinking, I realized that my accusations were actually wrong.
    The true meaning of his max_same is the window_size. (i.e. windows_size = max_same + k).
    So it is all right that window_size never decreases since we are only interested in finding the biggest window.
    For return size - start;, it is basically returning the window_size, since the biggest window we've found will eventually slide to position [start, size).


  • 1
    W

    Not totally understanding your solution. As for me, I would like to write the code in this way:

    class Solution {
    public:
        int characterReplacement(string s, int k) {
            int i = 0, j = 0, ctr[91] = {};
            int res = 0;
            while (j < s.size()) {
                ctr[s[j++]]++;
                while (j-i - *max_element(ctr+65, ctr+91) > k)
                    ctr[s[i++]]--;
                res = max(j-i, res);
            }
            return res;
            
        }
    };
    

    I had thought your solution was wrong, but after I tried several test cases it just amazingly works fine. I still need some time to think out why.


  • 0
    D

    @StefanPochmann As always, amazing code. If you code like this, the interviewer will get frustrated and angry because most people couldn't follow your thought at first time. I changed the coding style and hope it can help a little bit.

    class Solution {
    public:
        int characterReplacement(string s, int k) {
            vector<int> m(128, 0);
            int count = 0, begin = 0, end = 0, d = 0;
            while(end < s.size())
            {
                m[s[end]]++;
                if (m[s[end]] > count) count = m[s[end]];
                end++;
                if (end - begin - count > k)
                {
                    m[s[begin]]--;
                    begin++;
                }
            }
            d = end - begin;
            return d;
        }
    };
    

  • 0
    D

    @wangm12 You don't need to use while (j-i - *max_element(ctr+65, ctr+91) > k)
    you can use if (j-i - *max_element(ctr+65, ctr+91) > k) as Stefan used. Then you may understand Stefan's approach more easily.


  • 0
    F

    @clydexu
    I have come up with nearly exactly the same code as yours lol:
    https://discuss.leetcode.com/topic/92084/6-line-c-o-n-not-o-26n-time-o-26-space-solution

    The only difference is:

    1. You have an unnecessary "result" variable.
    2. You used char[256] space while mine uses only char[26] (there are only uppercase letters).

  • 0
    S

    Although your solution is very concise, it does not seem to implement the requirements.
    Find the length of a longest substring containing all repeating letters.
    But you've only computed repeating letters in the window.
    For example, s = "AABABBAAAAAA", k=1. In accordance with the title requirements, result = 4, but the solution will output 7.
    Maybe I understood it wrong, ha ha.


  • 0

    @spring_flower I have no idea why you think the result should be 4.


Log in to reply
 

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