“This is the 22nd day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

Topic describes

You are given two strings of the same length, S and T.

S in the case of a character I get to the t of the characters I need [I] – [I] t | s | overhead (overhead may be 0), which is two characters in the ASCII value of the absolute value of difference.

The maximum budget for a change string is maxCost. When converting a string, the total cost should be less than or equal to that budget, which means that the conversion of the string may be incomplete.

Return the maximum length that can be converted if you can convert a substring of S to its corresponding substring of t.

If there is no substring in S that can be converted to a corresponding substring in t, 0 is returned.

Example 1:

Input: s = “abcd”, t = “BCDF “, maxCost = 3 Output: 3 Explanation:” ABC “in S can be changed to” BCD “. The cost is 3, so the maximum length is 3.

Example 2:

Input: s = “abcd”, t = “cdef”, maxCost = 3 Output: 1 Explanation: The cost of any character in S to become the corresponding character in T is 2. So, the maximum length is 1.

Analysis of the

In fact, it’s important to understand the meaning of this question. In particular, the string s of the same length as t in the question must be in the same position in T after each character change, and the substring must be continuous. For example, if s=”abcz”, t=”zabc”, maxCost=0 (that is, without changing the characters in s), the return value should be 0 instead of 3. For the problem of finding the maximum length of continuous subsequence satisfying the condition, the sliding window method immediately comes to mind.

Train of thought
  • Mark the left and right ends of the sliding window with L and R, and the sliding window with length (i.e. the number of elements in the window) of R-L +1.
  • Set the sum of elements in the sliding window as WS, take the position r at the right end of the window as the priority moving object, the left endpoint L follows the right endpoint R, and ensure that the sum of elements in the window does not exceed maxCost.
  • After each r traversal, the ans needs to be updated in time.
var equalSubstring = function(s, t, maxCost) {
    let stemp = s.split("");
    let ttemp = t.split("");
    let result = 0;
    let left = 0,right = 0;
    let usedCost = 0;
    let tempList = [];
    for(let i = 0 ; i< stemp.length; i++) {
        tempList.push(Math.abs(stemp[i].charCodeAt() - ttemp[i].charCodeAt()));
    }
    while(right< stemp.length) {
        const val = tempList[right];
        if(usedCost + val > maxCost) {// The right pointer has already been incremented and val is the next value of val
           usedCost = usedCost - tempList[left];
            left ++;
        } else {
            usedCost = usedCost + val;
            right++;
        }
        result = Math.max(result, right - left);
    }
   
    return result;
};
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤