Two Concise C++ Solution: 9ms 11 lines and 20ms 7 lines


  • 2
    1. 9ms Sliding window solution.
      modified max(res, j - i) to max(res, j - i + min(i, times)), as it might also extend to the left.
    int characterReplacement(string s, int k) {
        int i = 0, j = 0, times = k, res = 0, cache[26] = {};
        for (; j < s.size(); j++) {
            cache[s[j] - 'A']++;
            if (s[j] != s[i] && times-- == 0) {
                res = max(res, j - i);
                while (i < j && j - i - cache[s[i] - 'A'] >= k) 
                    cache[s[i++] - 'A']--;
                times = k - j + i - 1 + cache[s[i] - 'A'];
            }
        }
        return max(res, j - i + min(i, times));
    }
    
    1. 20ms Solution based on @StefanPochmann solution, Thanks
    int characterReplacement(string s, int k) {
        int i = 0, j = 0, maxCount = 0, cache[26] = {};
        while (j < s.size()) {
            maxCount = max(maxCount, ++cache[s[j++] - 'A']);
            if (j - i - maxCount > k && cache[s[i++] - 'A']-- == maxCount) 
                maxCount = *max_element(cache, cache + 26);
        }
        return j - i;
    }
    

  • 0
    D

    Correct me if I am wrong, but the code does not pass this case:
    "ABBB"
    2
    code return 3 but result is 4


  • 0

    This is definitely not correct. It assumes that it's always the first character in the substring that is not replaced, whereas it's not necessary so. For example: "BAAAB", 2. The correct answer is 5 (replace the first and the last B), but this solution gives 8.


  • 0

    @deckstream
    Sorry. I thought it was corrected, as it passed the test cases in contest.
    Just modified max(res, j - i) to max(res, j - i + min(i, times))
    I think it works now. Correct me if it is wrong.
    Thank you.


  • 0

    @SergeyTachenov
    Just modified.
    max(res, j - i) to max(res, j - i + min(i, times))


  • 0
    F

    @zyoppy008
    Your code has the same problem as StefanPochmann's.
    maxCount = *max_element(cache, cache + 26);
    this is redundant.
    You can just keep a record of maxCount when ever cache[j] ++;


Log in to reply
 

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