1208. Get Equal Substrings Within Budget LeetCode Solution

In this guide, you will get 1208. Get Equal Substrings Within Budget LeetCode Solution with the best time and space complexity. The solution to Get Equal Substrings Within Budget problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Get Equal Substrings Within Budget solution in C++
  4. Get Equal Substrings Within Budget solution in Java
  5. Get Equal Substrings Within Budget solution in Python
  6. Additional Resources
1208. Get Equal Substrings Within Budget LeetCode Solution image

Problem Statement of Get Equal Substrings Within Budget

You are given two strings s and t of the same length and an integer maxCost.
You want to change s to t. Changing the ith character of s to ith character of t costs |s[i] – t[i]| (i.e., the absolute difference between the ASCII values of the characters).
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 character in t, so the maximum length is 1.

Example 3:

See also  403. Frog Jump LeetCode Solution

Input: s = “abcd”, t = “acde”, maxCost = 0
Output: 1
Explanation: You cannot make any change, so the maximum length is 1.

Constraints:

1 <= s.length <= 105
t.length == s.length
0 <= maxCost <= 106
s and t consist of only lowercase English letters.

Complexity Analysis

  • Time Complexity:
  • Space Complexity:

1208. Get Equal Substrings Within Budget LeetCode Solution in C++

class Solution {
 public:
  int equalSubstring(string s, string t, int maxCost) {
    int j = 0;
    for (int i = 0; i < s.length(); ++i) {
      maxCost -= abs(s[i] - t[i]);
      if (maxCost < 0)
        maxCost += abs(s[j] - t[j++]);
    }

    return s.length() - j;
  }
};
/* code provided by PROGIEZ */

1208. Get Equal Substrings Within Budget LeetCode Solution in Java

class Solution {
  public int equalSubstring(String s, String t, int maxCost) {
    int j = 0;
    for (int i = 0; i < s.length(); ++i) {
      maxCost -= Math.abs(s.charAt(i) - t.charAt(i));
      if (maxCost < 0)
        maxCost += Math.abs(s.charAt(j) - t.charAt(j++));
    }

    return s.length() - j;
  }
}
// code provided by PROGIEZ

1208. Get Equal Substrings Within Budget LeetCode Solution in Python

class Solution:
  def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
    j = 0
    for i in range(len(s)):
      maxCost -= abs(ord(s[i]) - ord(t[i]))
      if maxCost < 0:
        maxCost += abs(ord(s[j]) - ord(t[j]))
        j += 1

    return len(s) - j
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: