## 424 Longest Repeating Character Replacement

>[424. Longest Repeating Character Replacement
](https://leetcode.com/problems/longest-repeating-character-replacement/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

:::spoiler *Sharing order (random)*
1. YCLee
2. 東
3. SOL
:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
    let left = 0;
    let right = 0;
    let maxLen = 1;
    let highestFrequency = 0;
    const frequencies = {};
    while(right < s.length){
        const char = s[right];

        if(char in frequencies){
            frequencies[char]++;
        }else{
            frequencies[char] = 1;
        }

        highestFrequency = Math.max(highestFrequency, frequencies[char]);

        if((right - left + 1) - highestFrequency - k > 0){
            const leftChar = s[left];
            frequencies[leftChar]--;
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
        right++;

    }
    return maxLen;
};

:::

<hr/>

### Sol
- slide window size - max count <= replacement count
:::spoiler Code

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
    const count = {}
    let result = 0;
    let left = 0;
    let right = 0;
    while(right < s.length){
        count[s[right]] = (count[s[right]] || 0) + 1
        const maxCount =  Math.max(...Object.values(count))
        if (!((right + 1 - left ) - maxCount <= k)){
            count[s[left]]--;
            left++
        }
        
        result = Math.max(result, right + 1 -left)
        right++
        
    }
    return result
};

:::

<hr/>

### 東

:::spoiler Code

var characterReplacement = function(s, k) {
    let start = 0;
    let freqMap = {};
    let maxFreq = 0;
    let result = 0;
    for(let end = 0; end < s.length; end++){
        freqMap[s[end]] ||= 0;
        freqMap[s[end]]++;

        maxFreq = Math.max(maxFreq, freqMap[s[end]]);

        const isValid = (end - start + 1 - maxFreq <= k);
        if(!isValid){
            freqMap[s[start]]--;
            start++;
        }
        result = end - start + 1;
    }
    return result;
};

:::

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::