Get Equal Substrings Within Budget

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 i^th character of S to the i^th 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 i^th index and the j^th 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;
}

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