DEV Community

Cover image for Longest Repeating Character Replacement Explanation
ramnayan
ramnayan

Posted on • Edited on

Longest Repeating Character Replacement Explanation

I'm writing this post about an specific data structure and algorithm well known problem that is "Longest Repeating Character Replacement".

I have tried to solve this problem with javascript and using two popular algorithm that is Two-Pointer & Sliding-Window.

I hope you are aware of these two algorithms. if you don't know don't worry bellow i have mention the blogs link you can explore or you can find on the google.

Two Pointer - https://www.geeksforgeeks.org/dsa/two-pointers-technique/

Sliding Window - https://www.geeksforgeeks.org/dsa/window-sliding-technique/

Problem start here********

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.
Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

Explanation*************

Initialise the required variables left right maxLength maxChar and count.

first loop start from string zero index that is right & right. left start when K become zero or (r-l+1)-maxChar>K condition true it means window shrinking.

count variable stores the character frequency to find the maxChar.

var characterReplacement = function(s, k) {
        if(s.length==1) return 1;
        let l=r=maxChar=maxLength=0;
        let count={};

        for(let r=0; r<s.length;r++){
             if(s[r] in count){
                ....
            }else ....;
            maxChar = Math.max(maxChar, count[s[r]]);
            while((r-l+1)-maxChar>k){
                .....
            }
            maxLength=Math.max(maxLength, (r-l+1));
        }
        return maxLength;
};
Enter fullscreen mode Exit fullscreen mode

This is the my best approach that i have used if you have any suggestions please put your thought.

Thanks for stay to the end👍🙈

Top comments (0)