1.
Introduction
1.1.
Problem Statement
1.2.
Example
2.
Using Prefix Array
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Program
2.2.2.
Input
2.2.3.
Output
2.3.
Time Complexity
2.4.
Space Complexity
3.
Using Sliding Window Technique
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Program
3.2.2.
Input
3.2.3.
Output
3.3.
Time Complexity
3.4.
Space Complexity
4.
Key Takeaways
Last Updated: Mar 27, 2024

# Get Equal Substrings Within Budget

Ishita Chawla
1 upvote

## 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

You are given 2 strings, ‘S’ and ‘T’ of the same length. Changing the ith character of S to the ith character of T costs |S[i] - T[i]|, i.e, the absolute difference of the ASCII values of these characters.

Your task is to find the maximum length of a substring of S that can be converted into a substring of T, with a cost less than or equal to a given maximum cost, MAXCOST.

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

Also read - abs in C++

### Example

•      S = ‘abcd’

T = ‘bcdf’

MAXCOST = 3

‘abc’ of string S can be converted into ‘bcd’ of string T and the maximum cost is 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

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

#### 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);
}

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

#### 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++

## Key Takeaways

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 ForceStrings and crack your interviews like a Ninja!

Check out this problem - Multiply Strings

Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.

In case of any comments or suggestions, feel free to post them in the comments section.

Live masterclass