Using Prefix Array
The main idea is to store the absolute sum of the strings in a prefix array of length N. This will store the cost of changing a character of string S to that of string T.
Algorithm
- Maintain 2 pointers, i and j.
- Check whether the difference between the ith index and the jth index of the prefix array is more than MAXCOST using a while loop.
- If this difference is greater, then increase the pointer j to compensate for this cost, else pointer i is increased.
Implementation
Program
// C++ program to get equal substrings within budget.
#include <iostream>
using namespace std;
// Function to find the maximum length of the substring.
int equalSubstring(string s, string t, int maxCost)
{
int n = s.length();
// Declaring a prefix array.
int prefixSum[n + 1] = {0};
// Variable to store the maximum length.
int sol = 0;
// Filling the prefix array.
for (int i = 1; i <= n; i++)
{
prefixSum[i] = prefixSum[i - 1] + abs(s[i - 1] - t[i - 1]);
}
int j = 0;
// To find the maximum length.
for (int i = 1; i <= n; i++)
{
while ((prefixSum[i] - prefixSum[j]) > maxCost)
{
j++;
}
// Update the maximum length
sol = max(sol, i - j);
}
return sol;
}
int main()
{
string s, t;
int maxCost;
// Taking user input.
cout << "Enter the first string: ";
cin >> s;
cout << "Enter the second string: ";
cin >> t;
cout << "Enter the budget: ";
cin >> maxCost;
cout << "The maximum length of the substring is " << equalSubstring(s, t, maxCost) << "\n";
return 0;
}
You can also try this code with Online C++ Compiler
Input
Enter the first string: abcd
Enter the second string: bcdf
Enter the budget: 3
Output
The maximum length of the substring is 3.
Time Complexity
The time complexity of this approach is O(N), where N is the length of the strings.
Since we traverse the entire string of length N, the time complexity is O(N).
Space Complexity
The space complexity of this approach is O(N), where N is the length of the strings.
We consider a prefix array of length N + 1 to store the absolute difference between the characters. So the space complexity is given by O(N).
Also see, Euclid GCD Algorithm
Using Sliding Window Technique
Algorithm
- We take 2 variables, ‘ANS’ and ‘SUM’.
- We start storing the absolute sum of the strings in SUM and check whether it is greater than MAXCOST.
- If it is greater, the sum of the initial characters is subtracted until it becomes less than MAXCOST.
- Then, ANS is updated with the maximum answer at each step.
Implementation
Program
// C++ program to get equal substrings within budget.
#include <iostream>
using namespace std;
// Function to find the maximum length of the substring.
int equalSubstring(string s, string t, int maxCost)
{
int sum = 0, ans = 0, j = 0;
// To find the maximum length.
for (int i = 0; i < s.length(); i++)
{
sum += abs(s[i] - t[i]);
// Subtracting the cost of initial characters and finding the maximum.
while (sum > maxCost)
{
sum -= abs(s[j] - t[j]);
j++;
}
ans = max(ans, i - j + 1);
}
// Returning the answer.
return ans;
}
int main()
{
string s, t;
int maxCost;
// Taking user input.
cout << "Enter the first string: ";
cin >> s;
cout << "Enter the second string: ";
cin >> t;
cout << "Enter the budget: ";
cin >> maxCost;
// Calling the function and printing the answer.
cout << "The maximum length of the substring is " << equalSubstring(s, t, maxCost) << "\n";
return 0;
}
You can also try this code with Online C++ Compiler
Input
Enter the first string: abcd
Enter the second string: bcdf
Enter the budget: 3
Output
The maximum length of the substring is 3.
Time Complexity
The time complexity of this approach is O(N), where N is the length of the strings.
Since we traverse the entire string of length is N, the time complexity is O(N).
Space Complexity
The space complexity of this approach is O(1).
Since we are not taking any additional data structure to find the answer, the space complexity is constant and is given by O(N).
Also check out - Substr C++
Frequently Asked Questions
What is the "Get Equal Substrings Within Budget" problem?
The "Get Equal Substrings Within Budget" problem involves finding substrings of a given string that can be modified to match another substring within a specified budget. The budget refers to the number of allowed character changes for each substring comparison.
How do you approach solving the "Get Equal Substrings Within Budget" problem?
To solve this problem, we typically use a sliding window technique, comparing substrings of the given string and calculating the cost of transforming one substring into another. The goal is to ensure the transformation cost stays within the given budget.
What is the significance of the budget in this problem?
The budget in this problem limits the number of character changes you can make to transform one substring into another. This constraint plays a key role in determining whether a valid substring pair can be obtained, ensuring an efficient solution.
Conclusion
So, this blog discussed the problem of Get Equal Substrings Within Budget, using 2 different approaches, discussing each approach's time and space complexity. To learn more, head over right now to Coding Ninjas Studio to practice problems on topics like Greedy, Brute Force, Strings and crack your interviews like a Ninja!
Check out this problem - Multiply Strings
34+ registered 
