__Introduction__

__Introduction__

Strings are an essential topic of Data Structures and Algorithms, and having a solid grip over them is necessary. Strings are a part of almost every interview, and at least one question related to them is always asked in nearly all coding contests or interviews.

In this blog, we will be discussing one such essential but fundamental problem related to strings.

__Problem Statement__

__Problem Statement__You are given * 2* strings,

*and*

**‘S’***of the same length. Changing the*

**‘T’***character of S to the*

**i**^{th}*character of*

**i**^{th }*costs*

**T***, i.e, the absolute difference of the ASCII values of these characters.*

**|S[i] - T[i]|**Your task is to find the maximum length of a substring of * S* that can be converted into a substring of

*, with a cost less than or equal to a given maximum cost,*

**T**

**MAXCOST.**Note that if there is no such substring, you have to return * 0* as the answer.

Also read - __abs in C++__

__Example__

__Example__

**S = ‘abcd’**

**T = ‘bcdf’**

**MAXCOST = 3**

‘abc’ of string * S* can be converted into ‘bcd’ of string

*and the maximum cost is*

**T***.*

**3**So, the maximum length is * 3*.

**S = ‘abcd’**

**T = ‘cdef’**

**MAXCOST = 3**

Each character of * S* will cost 2 to be converted into

*.*

**T**So, the maximum length is * 1*.

**S = ‘abcd’**

**T = ‘axyx’**

**MAXCOST = 0**

No other character except ‘a’ can be changed.

So, the maximum length is * 0*.

__Using Prefix Array__

__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

*to that of string*

**S***.*

**T**__Algorithm__

__Algorithm__- Maintain
pointers,**2**and**i**.**j** - Check whether the difference between the
index and the**i**^{th}index of the prefix array is more than**j**^{th}using a while loop.**MAXCOST** - If this difference is greater, then increase the pointer
to compensate for this cost, else pointer**j**is increased.**i**

**Implementation**

**Implementation**

__Program__

__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;
}
```

__Input__

__Input__```
Enter the first string: abcd
Enter the second string: bcdf
Enter the budget: 3
```

__Output__

__Output__`The maximum length of the substring is 3.`

**Time Complexity**

**Time Complexity**

The time complexity of this approach is * O(N)*, where

*is the length of the strings.*

**N**Since we traverse the entire string of length * N*, the time complexity is

**O(N).****Space Complexity**

**Space Complexity**

The space complexity of this approach is * O(N)*, where

*is the length of the strings.*

**N**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__