Get Equal Substrings Within Budget

Updated on 30 May, 2025
Get Equal Substrings Within Budget header image

Problem Statement

The given problem involves two strings s and t of the same length and an integer maxCost. The goal is to transform s into t by modifying the characters with certain costs and find out the longest possible substring from s that can be transformed into a corresponding substring in t without exceeding the given maxCost. The cost for changing the ith character of s to the ith character of t is calculated as the absolute difference between their ASCII values. If there is no substring in s that can be changed to match a substring in t within the cost constraints, the function should return 0.

Examples

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.

Approach and Intuition

Understanding the problem through examples can build the correct intuition:

  1. Example 1:
    s = "abcd", t = "bcdf", maxCost = 3

    To transform "abcd" into "bcdf", the cost calculations are as follows:

    • Changing 'a' to 'b' costs |97 - 98| = 1
    • Changing 'b' to 'c' costs |98 - 99| = 1
    • Changing 'c' to 'd' costs |99 - 100| = 1
    • Changing 'd' to 'f' would cost |100 - 102| = 2

    Summing the costs for the first three characters equals 3, which matches the maxCost. Therefore, the longest substring has the length 3.

  2. Example 2:
    s = "abcd", t = "cdef", maxCost = 3

    Here, each character transformation costs 2:

    • Changing 'a' to 'c', 'b' to 'd', etc., each costs 2.

    Given a maxCost of 3, only one transformation is affordable, hence the longest substring length is 1.

  3. Example 3:
    s = "abcd", t = "acde", maxCost = 0

    Even minor transformations exceed the maxCost of 0. However, characters 'a' in both s and t are already same, thus length 1 is achievable without any cost.

Algorithm Insight:

The sliding window technique or two-pointer technique is useful in identifying the maximal length of the substring that can be changed under the maximum cost constraint. You initiate with a starting and ending pointer, move through the string while calculating the cost and adjusting the window size accordingly. This allows for optimal exploration of potential substrings in linear time complexity.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    int longestSubstrWithCostLimit(string src, string target, int limit) {
        int length = src.size();
        
        // Keeps track of the maximum length of substring with cost limit
        int maxLength = 0;
        // Initial starting position for each allowable substring
        int begin = 0;
        // Cost of converting substring in src to match target
        int ongoingCost = 0;

        for (int end = 0; end < length; end++) {
            // Increment cost for the new character discrepancy
            ongoingCost += abs(src[end] - target[end]);

            // Reduce the window size until the cost constraint is satisfied
            while (ongoingCost > limit) {
                ongoingCost -= abs(src[begin] - target[begin]);
                begin++;
            }

            // Compute maximum substring length as we iterate
            maxLength = max(maxLength, end - begin + 1);
        }

        return maxLength;
    }
};

The C++ code provided solves the problem of finding the maximum length of a substring where the cost of converting one string (src) to another target string (target) does not exceed a given budget (limit). The code efficiently uses a sliding window technique.

Here's a walkthrough of the solution implementation:

  • Initialize maxLength to zero to track the maximum length of any valid substring found.
  • The variables begin and ongoingCost track the starting index of the substring and the cumulative cost of transformations required to convert src to target, respectively.
  • Iterate through the string using a variable end to consider each new character in src.
  • For each character at position end, adjust the ongoingCost by adding the absolute difference between the characters at src[end] and target[end].
  • If the ongoingCost exceeds the limit, reduce the window size from the left by adjusting begin and decreasing ongoingCost accordingly, until the substring fits within the cost limit.
  • After adjusting, if needed, update maxLength to the maximum between its current value and the length of the current valid substring.
  • Continue this process for each character in the string src.

The function returns maxLength, representing the length of the longest substring meeting the specified budget constraint. This approach ensures that each index is processed in constant time, thus making the sliding window technique efficient for this problem.

java
class Solution {

    public int maxLengthSubstr(String str1, String str2, int maxCost) {
        int length = str1.length();

        int longest = 0;
        int windowStart = 0;
        int currentCost = 0;

        for (int i = 0; i < length; i++) {
            currentCost += Math.abs(str1.charAt(i) - str2.charAt(i));

            while (currentCost > maxCost) {
                currentCost -= Math.abs(str1.charAt(windowStart) - str2.charAt(windowStart));
                windowStart++;
            }

            longest = Math.max(longest, i - windowStart + 1);
        }

        return longest;
    }
}

This Java program is designed to find the maximum length of a substring that can be formed from two given strings, str1 and str2, under a certain cost constraint defined by maxCost. The cost is calculated based on the absolute difference between the characters of str1 and str2 at the same positions.

  • The maxLengthSubstr function initializes three variables:

    • length derives the length of the input strings (assumed to be equal).
    • longest keeps track of the length of the longest valid substring found.
    • windowStart marks the start of a sliding window while iterating through the strings.
    • currentCost maintains the running total of the cost within the window.
  • The loop iterates over each character position in the strings:

    • The cost of the current position is added to currentCost.
    • If currentCost exceeds maxCost, the loop adjusts the starting position of the window (windowStart) and subtracts the corresponding cost until currentCost is less than or equal to maxCost.
    • At each iteration, it updates the longest variable to store the maximum length of substrings that meet the cost condition.
  • The function finally returns the length of the longest valid substring.

This solution effectively uses a sliding window approach, optimizing the process of exploring possible substrings, resulting in not only a correct but also efficient way of finding the longest substring within the given budget. Ensure to handle edge cases, such as empty string inputs or inputs where no valid substring exists within the budget constraint.

python
class Solution:
    def maxEqualitySubstr(self, str1: str, str2: str, maxCost: int) -> int:
        length = len(str1)

        longest = 0
        start_index = 0
        current_cost = 0

        for index in range(length):
            current_cost += abs(ord(str1[index]) - ord(str2[index]))

            while current_cost > maxCost:
                current_cost -= abs(ord(str1[start_index]) - ord(str2[start_index]))
                start_index += 1

            longest = max(longest, index - start_index + 1)

        return longest

The provided Python solution focuses on finding the longest substring where the character transformation cost between two strings stays within a specified budget. The function maxEqualitySubstr accepts two strings, str1 and str2, and an integer maxCost that represents the maximum allowed total cost for transforming str1 into str2 by adjusting individual characters.

Here's how the solution achieves the objective:

  • The function starts by initializing variables length to determine the length of the strings, longest to keep track of the longest substring length found, start_index to mark the beginning of the current substring, and current_cost to track the accumulated cost of transformations.
  • A for loop iterates through each character index of the strings. The transformation cost for each character is computed using the absolute difference of their ASCII values and added to current_cost.
  • If current_cost exceeds maxCost, the algorithm reduces current_cost by removing the cost of the first character in the current substring and then moves the starting index forward.
  • At each step, it computes the length of the current substring and updates longest if the current substring length is greater.
  • Return the length of the longest substring that meets the cost constraint.

This method efficiently determines the maximum length of a substring where the sum of costs of changes required (from str1 to str2) does not exceed maxCost, utilizing a sliding window technique to maintain and adjust the substring under consideration.

Comments

No comments yet.