Scale Engineer

Get Equal Substrings Within Budget

Med
#1129Time: O(n^2), where n is the length of the strings. The two nested loops result in a quadratic number of operations as we check almost all possible substrings.Space: O(1), as we are not using any extra space that scales with the input size. The cost is calculated on the fly.1 company
Patterns
Sliding WindowPrefix Sum
Algorithms
Binary Search
Data structures
String
Companies
IBM

Prompt

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:

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach systematically checks every possible substring. For each substring, it calculates the total cost to transform the characters from string s to the corresponding characters in string t. If the calculated cost is within the maxCost budget, it updates the maximum length found so far.

Algorithm

  • Create an integer array costDiffs of the same length as s.
  • Iterate from i = 0 to s.length() - 1 and populate costDiffs[i] = Math.abs(s.charAt(i) - t.charAt(i)).
  • Initialize maxLength = 0.
  • Iterate with a start pointer from 0 to s.length() - 1.
    • Initialize currentCost = 0.
    • Iterate with an end pointer from start to s.length() - 1.
      • Add costDiffs[end] to currentCost.
      • If currentCost <= maxCost, it's a valid substring. Update maxLength = Math.max(maxLength, end - start + 1).
      • Else, the cost is too high. Break the inner loop since adding more characters will only increase the cost.
  • Return maxLength.

Walkthrough

First, we can simplify the problem by thinking about an array of costs. Let's define cost[i] = |s[i] - t[i]|. The problem is now equivalent to finding the longest contiguous subarray in this cost array whose sum does not exceed maxCost.

The brute-force method involves using two nested loops to define all possible subarrays. The outer loop sets the starting index (i) of the subarray, and the inner loop sets the ending index (j). For each subarray from i to j, we calculate its sum. To do this efficiently, we maintain a running sum (currentCost) in the inner loop. If currentCost is within the maxCost budget, the current subarray is valid, and we update our maxLength with its length (j - i + 1). If currentCost exceeds maxCost, we can immediately stop extending the current subarray (break the inner loop) because any longer subarray starting at i will also exceed the budget.

class Solution {    public int equalSubstring(String s, String t, int maxCost) {        int n = s.length();        int maxLength = 0;         for (int i = 0; i < n; i++) {            int currentCost = 0;            for (int j = i; j < n; j++) {                currentCost += Math.abs(s.charAt(j) - t.charAt(j));                if (currentCost <= maxCost) {                    maxLength = Math.max(maxLength, j - i + 1);                } else {                    // Pruning: if cost exceeds, no need to extend this substring further                    break;                }            }        }        return maxLength;    }}

Complexity

Time

O(n^2), where n is the length of the strings. The two nested loops result in a quadratic number of operations as we check almost all possible substrings.

Space

O(1), as we are not using any extra space that scales with the input size. The cost is calculated on the fly.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correct for all inputs, though slow.

Cons

  • Highly inefficient for large inputs due to its quadratic time complexity.

  • Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.

Solutions

class Solution {private  int maxCost;private  int[] f;private  int n;public  int equalSubstring(String s, String t, int maxCost) {    n = s.length();    f = new int[n + 1];    this.maxCost = maxCost;    for (int i = 0; i < n; ++i) {      int x = Math.abs(s.charAt(i) - t.charAt(i));      f[i + 1] = f[i] + x;    }    int l = 0, r = n;    while (l < r) {      int mid = (l + r + 1) >>> 1;      if (check(mid)) {        l = mid;      } else {        r = mid - 1;      }    }    return l;  }private  boolean check(int x) {    for (int i = 0; i + x - 1 < n; ++i) {      int j = i + x - 1;      if (f[j + 1] - f[i] <= maxCost) {        return true;      }    }    return false;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem