
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
andt
consist of only lowercase English letters.
Approach and Intuition
Understanding the problem through examples can build the correct intuition:
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 themaxCost
. Therefore, the longest substring has the length3
.- Changing 'a' to 'b' costs
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
of3
, only one transformation is affordable, hence the longest substring length is1
.- Changing 'a' to 'c', 'b' to 'd', etc., each costs
Example 3:
s = "abcd"
,t = "acde"
,maxCost = 0
Even minor transformations exceed the
maxCost
of0
. However, characters 'a' in boths
andt
are already same, thus length1
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
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
andongoingCost
track the starting index of the substring and the cumulative cost of transformations required to convertsrc
totarget
, respectively. - Iterate through the string using a variable
end
to consider each new character insrc
. - For each character at position
end
, adjust theongoingCost
by adding the absolute difference between the characters atsrc[end]
andtarget[end]
. - If the
ongoingCost
exceeds thelimit
, reduce the window size from the left by adjustingbegin
and decreasingongoingCost
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.
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
exceedsmaxCost
, the loop adjusts the starting position of the window (windowStart
) and subtracts the corresponding cost untilcurrentCost
is less than or equal tomaxCost
. - At each iteration, it updates the
longest
variable to store the maximum length of substrings that meet the cost condition.
- The cost of the current position is added to
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.
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, andcurrent_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
exceedsmaxCost
, the algorithm reducescurrent_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.
No comments yet.