This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

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 Description: The" ABC "in S can change to" BCD ". The cost is 3, so the maximum length is 3. Source: LeetCode Link: https://leetcode-cn.com/problems/get-equal-substrings-within-budget Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • This topic is relatively long, need to read carefully, after careful analysis, split into sub-problems to solve.
  • First, find the different parts of the two strings.
  • Second, compare the difference between the different parts and the maximum cost to find the maximum length. You can do this with the idea of sliding Windows, and I didn’t think of sliding Windows when I did this problem. It is after reading the prompts in the problem that sliding Windows are used to solve such problems.

AC code

public class DayCode { public static void main(String[] args) { String s = "abcd", t = "bcdf"; int maxCost = 3; int ans = new DayCode().equalSubstring(s, t, maxCost); System.out.println("ans is " + ans); } /** * https://leetcode-cn.com/problems/get-equal-substrings-within-budget/ * @param s * @param t * @param maxCost * @return */ public int equalSubstring(String s, String t, int maxCost) { int n = s.length(); int[] diff = new int[n]; for (int i = 0; i < n; i++) { diff[i] = Math.abs(s.charAt(i) - t.charAt(i)); } int maxLength = 0; int start = 0, end = 0; int sum = 0; while (end < n) { sum += diff[end]; while (sum > maxCost) { sum -= diff[start]; start++; } maxLength = Math.max(maxLength, end - start + 1); end++; } return maxLength; }}Copy the code

Submit tests:

AC smoothly!

conclusion

  • This code is O(n) in time and O(n) in space
  • Algorithm topics need careful analysis, repeated thinking, in order to master the secrets!
  • Stick to the daily question, come on!