Sponsored
Sponsored
This approach uses the sliding window technique to efficiently determine the maximum substring length that can be changed within the given cost. We maintain a window of characters from the strings s and t and slide it over the strings. We continuously calculate the cost for converting the current window substring from s to t. Whenever the cost exceeds maxCost, we shrink the window from the left to keep the cost under control. The maximum width of this window during traversal is the answer.
Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(1), as the solution uses only a fixed amount of extra space.
1#include <iostream>
2#include <string>
3#include <cmath>
4#include <algorithm>
5using namespace std;
6
7int equalSubstring(string s, string t, int maxCost) {
8 int start = 0, cost = 0, maxLength = 0;
9
10 for (int end = 0; end < s.size(); ++end) {
11 cost += abs(s[end] - t[end]);
12 while (cost > maxCost) {
13 cost -= abs(s[start] - t[start]);
14 start++;
15 }
16 maxLength = max(maxLength, end - start + 1);
17 }
18
19 return maxLength;
20}
21
22int main() {
23 string s = "abcd";
24 string t = "bcdf";
25 int maxCost = 3;
26 cout << equalSubstring(s, t, maxCost) << endl;
27 return 0;
28}The solution for C++ is similar to that in C. We use a loop to iterate through the string s using an endpoint index. We add the absolute difference of s[end] and t[end] to the cost. Whenever the cost exceeds maxCost, we shift the window by incrementing the start index, reducing cost accordingly. We keep updating the maximum length of the window that satisfies our cost limit and return it at the end.
This approach makes use of the prefix sum array to store accumulated costs and binary search to find the furthest valid endpoint for every starting point. First, calculate the prefix sum that stores the total cost from the beginning to any character index. Then, for each start point, use binary search to find the furthest valid end point where the total transformation cost still doesn't exceed maxCost.
Time Complexity: O(n log n), where n is the length of the string s due to the binary search iterations for each starting point.
Space Complexity: O(n), as it requires space for the prefix sum array.
public class Solution {
public int EqualSubstring(string s, string t, int maxCost) {
int n = s.Length;
int[] prefixSum = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + Math.Abs(s[i] - t[i]);
}
int maxLength = 0;
for (int start = 0; start < n; start++) {
int end = Array.BinarySearch(prefixSum, start + 1, n - start, prefixSum[start] + maxCost);
if (end < 0) end = ~end - 1;
maxLength = Math.Max(maxLength, end - start);
}
return maxLength;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.EqualSubstring("abcd", "bcdf", 3));
}
}The C# solution leverages a prefix sum and performs binary searches over it using the .NET framework's built-in methods. It efficiently finds the furthest substring satisfying the cost constraints, adaptive for high input limits due to logarithmic search complexity.