Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1208.html

1208. Get Equal Substrings Within Budget

Level

Medium

Description

You are given two strings s and t of the same length. You want to change s to t. Changing the i-th character of s to i-th character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.

You are also given an integer maxCost.

Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of t with a cost less than or equal to maxCost.

If there is no substring from s that can be changed to its corresponding substring from t, return 0.

Example 1:

Input: s = “abcd”, t = “bcdf”, maxCost = 3

Output: 3

Explanation: “abc” of s can change to “bcd”. That costs 3, so the maximum length is 3.

Example 2:

Input: s = “abcd”, t = “cdef”, maxCost = 3

Output: 1

Explanation: Each character in s costs 2 to change to charactor in t, so the maximum length is 1.

Example 3:

Input: s = “abcd”, t = “acde”, maxCost = 0

Output: 1

Explanation: You can’t make any change, so the maximum length is 1.

Constraints:

• 1 <= s.length, t.length <= 10^5
• 0 <= maxCost <= 10^6
• s and t only contain lower case English letters.

Solution

Create an array differences which has length the same as the length of s and t, where differences[i] is the absolute difference between s.charAt(i) and t.charAt(i). Then the problem is converted to another form. Find the length of the longest subarray from differences such that the sum of all the elements in the subarray is less than or equal to maxCost.

Use two pointers start and end, which point to 0 initially. If differences[0] <= maxCost, then the length of the longest subarray is at least 1. Each time append a new element to the subarray by moving end forward. If the subarray’s sum is greater than maxCost, then remove start forward to reduce the subarray’s length until the subarray’s sum is less than or equal to maxCost. After this, update the length of the longest subarray. After the whole array is looped over, return the length of the longest subarray.

• Java
• C++
• Python
• Go

• class Solution {
      public int equalSubstring(String s, String t, int maxCost) {
          int length = s.length();
          int[] differences = new int[length];
          for (int i = 0; i < length; i++) {
              char c1 = s.charAt(i), c2 = t.charAt(i);
              differences[i] = Math.abs(c1 - c2);
          }
          int maxLength = 0;
          int start = 0, end = 0;
          int sum = differences[0];
          if (sum <= maxCost)
              maxLength = 1;
          while (end < length - 1) {
              sum += differences[++end];
              while (sum > maxCost)
                  sum -= differences[start++];
              maxLength = Math.max(maxLength, end - start + 1);
          }
          return maxLength;
      }
  }
  

• // OJ: https://leetcode.com/problems/get-equal-substrings-within-budget/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      int equalSubstring(string s, string t, int maxCost) {
          int i = 0, j = 0, N = s.size(), cost = 0, ans = 0;
          for (; j < N; ++j) {
              cost += abs(s[j] - t[j]);
              for (; cost > maxCost; ++i) cost -= abs(s[i] - t[i]);
              ans = max(ans, j - i + 1);
          }
          return ans;
      }
  };
  

• class Solution:
      def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
          n = len(s)
          presum = [0] * (n + 1)
          for i in range(n):
              presum[i + 1] = presum[i] + abs(ord(s[i]) - ord(t[i]))
          left, right = 0, n
  
          def check(l):
              i = 0
              while i + l - 1 < n:
                  j = i + l - 1
                  if presum[j + 1] - presum[i] <= maxCost:
                      return True
                  i += 1
              return False
  
          while left < right:
              mid = (left + right + 1) >> 1
              if check(mid):
                  left = mid
              else:
                  right = mid - 1
          return left
  
  ############
  
  def findSubArray(nums):
      N = len(nums) # 数组/字符串长度
      left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
      sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
      res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
      while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
          sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
          while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
              sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
              left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
          # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
          res = max(res, right - left + 1) # 需要更新结果
          right += 1 # 移动右指针，去探索新的区间
      return res
  

• func equalSubstring(s string, t string, maxCost int) (ans int) {
  	var sum, j int
  	for i := range s {
  		sum += abs(int(s[i]) - int(t[i]))
  		for ; sum > maxCost; j++ {
  			sum -= abs(int(s[j]) - int(t[j]))
  		}
  		if ans < i-j+1 {
  			ans = i - j + 1
  		}
  	}
  	return
  }
  
  func abs(x int) int {
  	if x < 0 {
  		return -x
  	}
  	return x
  }
  

All Problems

All Solutions