c++ solution, with some explanation


  • 0
    T

    Based on some popular posts in LC, the idea is to find the longest substring, which satisfies (length - max_freq <= k); meaning there're at most k different chars;

    Here both solutions uses sliding window idea to maintain the substring; but different with other questions, when the sliding window increase by 1, 2 cases might happens: the condition holds, then the length of longest substring also increase by 1; otherwise, window side keeps the same, by increasing left index by 1, and update freq at the same time; so the final result only depends on the left index,l, and the string length sz

    class Solution1 {
    public:
        int characterReplacement(string s, int k) {
            int freq[126] = {0}, max_freq = 0, rst = 0;
            for (int i = 0, l = 0; i < s.size(); ++i) {
                max_freq = max(max_freq, ++freq[s[i]]);
                if (i-l+1 - max_freq > k) {
                    --freq[s[l++]];
                }
                rst = max(rst, i-l+1);
            }
            return rst;
        }
    };
    class Solution {
    public:
        int characterReplacement(string s, int k) {
            int freq[126] = {0}, max_freq = 0, l = 0;
            for (int i = 0; i < s.size(); ++i) {
                max_freq = max(max_freq, ++freq[s[i]]);
                if (i-l+1 - max_freq > k) {
                    --freq[s[l++]];
                }
            }
            return s.size() - l;
        }
    };
    

Log in to reply
 

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