Ninja and his Strings

Problem statement

Ninja has stored his strings in an array ‘A’ containing ‘N’ strings and their prices in an array ‘B’ containing ‘N’ integers such that the price of string ‘A[i]’ is equal to ‘B[i]’. Also, it is guaranteed that |A[i]| <= 26

For a given string ‘S’, he calculates its value using the above strings and their prices using the formula - 

              value(S) = ∑₀^N-1(F_i(‘a’) * B[i])                                                         (1)

Here, fi(S) = Number of substrings of S that are equal to string A[i]

          B[i] = Price of string A[i]

We have been given two strings ‘X’ and ‘Y’ and we can create a string ‘S’ by - 

S = substr(X) + substr(Y)                                                                              (2)

Here, substr(X) = Any substring of X (possibly empty)

          substr(Y) = Any substring of Y (possibly empty)

          And ‘+’ denotes the concatenation of two strings.

The task is to find the maximum value calculated using the given equation (1) with any string ‘S’ created by using equation (2).

Let’s take an example to understand the problem.

Suppose N = 3 and the strings of Ninja and their prices are given b the following arrays: 

A = {“ab”, “a”, “b”}

B = {2, 3, 1}

Also, given X = “bab” and Y = “ab”

We have to find the maximum value given by equation -

    value(S) = ∑₀^N-1(F_i(‘a’) * B[i])

We know that we can create string S by using the substrings of X and Y.

All the substrings of X = {“b”, “ba”, “bab”, “a”, “ab” }

All the substrings of Y = {“a”, “ab”, “b”}

S = substr(X) + substr(Y), where substr(str) = Any substring of ‘str’ (possibly empty)

So, all the possible value of S = {“”, “a”, “ab”, “b”, “ba”, “bab”, “bb”, “baa”, “baab”, “bab”, “baba”, “babab”, “babb”, “aa”, “aab”, “aba”, “abab”, “abb”}

Now, we have to find the value of each of these possible ‘S’ and find the maximum value among them.

Let’s calculate the value of each of the strings of the array -

S = {“”, “a”, “ab”, “b”, “ba”, “bab”, “bb”, “baa”, “baab”, “bab”, “baba”, “babab”, “babb”, “aa”, “aab”, “aba”, “abab”, “abb”}

We can calculate value of string “a” in the following way:

value(“a”) = ∑₀^N-1(F_i(‘a’) * B[i]) 

= ∑₀^N-1(Number of substrings of ‘a’ that are equal to A[i] * B[i])

= ((Number of substrings of “a” equal to A[0]) * B[0]) + (Number of substrings of “a” equal to A[1]) * B[1]) + (Number of substrings of “a” equal to A[2]) * B[2]))

= ((Number of substrings of “a” equal to “ab”) * B[0]) + (Number of substrings of “a” equal to “a”) * B[1]) + (Number of substrings of “a” equal to “b”) * B[2]))
= ((0 * 2) + (1 * 3) + (0 * 1))

= 3

Similarly, calculate the values of each of the possible strings ‘S’ and find the maximum among them.

Now that we understand the problem let's discuss the approach to solve it in the next section.

Also see, Euclid GCD Algorithm

Brute Force Approach

This section will discuss the brute force approach to find the maximum value of a string generated by concatenating any substring of X with any substring of Y. The simple approach is to first generate all the possible strings ‘S’ by concatenating each substring of X with each substring of Y. Then calculate the value of each of these strings using the given equation (1) and find the maximum among them. 

Algorithm

Step 1. First, the main function. Inside the main function, create variables and store the given values of ‘N’ , arrays ‘A’ and ‘B’ , and strings ‘X’ and ‘Y’. Then calculate the lengths of X and Y and call the function to find all the substrings of X and Y. Then create a variable ‘maxValue’ to store the maximum value of a string generated by concatenating any substring of X with any substring of Y. Then concatenate each substring of ‘X’ with each substring of ‘Y’ to get ‘S’ and call the function to calculate the value of ‘S’ and keep updating the value of variable ‘maxValue’.

Step 2. Next, create the function “findSubstrings()”, which takes a string and its length as inputs and returns the vector of strings containing all the substrings of the given string. Inside the function, create a “for loop” which runs for the length of the substring from 1 to N and then create two more “for loops” inside it to take the value of starting and ending indices of the substring. Generate each substring and store it into a vector and finally return the vector containing all the substrings.

Step 3. Next, create the function “findValue()” to find the value of a string which takes the following inputs:

1. A : array of strings that Ninja have
2. B: array containing prices of strings that Ninja have
3. N: number of strings that Ninja have
4. S: string whose value is to be calculated

Inside the function, run a “for loop” from i = 0 to i = N - 1 to calculate the value given by the equation - 

                               value(S) = i = 0N-1(fi(S) * B[i])

To get the value of fi(S), call the function “f()” which takes ‘S’ and ‘A[i]’ as input.

Step 4.  Finally, create the function “f()” which takes strings ‘S’ and ‘A[i]’ as input and returns the count of substrings of ‘S’ that are equal to A[i]. Inside the function, first call the function “findSubstrings()” to find all the substrings of ‘S’.Then create a variable ‘count = 0’ , traverse through all the substrings of ‘S’ and increase the value of count if any substring is equal to A[i]. After traversing through all the substrings of ‘S’, return the variable ‘count’.

C++ code

/*
   C++ program to find the  find the maximum value of a string generated by concatenating any 
   substring of X with any substring of Y
*/
#include <bits/stdc++.h>
using namespace std;


// Function to return all the substrings f str
vector<string> findSubstrings(string str, int n)
{
vector<string> ans;

for(int len = 1; len <= n; len++)
{
  for(int i = 0; i <= n-len; i++)
  {
    int j = i + len - 1;  
    string s;
            for (int k = i; k <= j; k++)
              {
                s.push_back(str[k]);
              }
            ans.push_back(s);
  }
}
 
    return ans;
}


// Function to return the number of substrings of S that are equal to Ai
int f(string S, string Ai)
{
int lenS = S.length();
vector<string> substrS = findSubstrings(S, lenS);

int count = 0;
for(int i=0; i<substrS.size(); i++)
  {
   if(substrS[i] == Ai) {
     count++;
   }
  }
    return count;
}


// Function to return the maximum value of the string S Calculated using the formula given in the question
int findValue(string A[], int B[], int N, string S)
{
   int val = 0;
   
   for(int i=0; i<N; i++)
     {
      val = val + (f(S, A[i]) * B[i]); 
     }
     
   return val;
}


// Main function
int main() 
{


// Number of strings that Ninja have
int N = 3;

// Given Ninja's strings
string A[3] = {"ab", "a", "b"};

// Given Prices of strings of Ninja
int B[3] = {2, 3, 1};

// Given strings whose substrings are used to generate string S
string X = "bab";
string Y = "ab";

// Calculating the lengths of X and Y
int lenX = X.length();
int lenY = Y.length();

// Call the function to find all the substrings of X 
vector<string> substrX = findSubstrings(X, lenX);

// Call the function to find all the substrings of Y 
vector<string> substrY = findSubstrings(Y, lenY);

// Variable to store the maximum value
int maxValue = 0;

// Concatenate every substring of X with every substring of Y to get S and calculate its value
for(int i = 0; i < substrX.size(); i++)
{
  for(int j = 0; j < substrY.size(); j++)
    {
     string S = substrX[i] + substrY[j];
      
     // Call the function to calculate value of S
     int val = findValue(A, B, N, S);
      
     // Update the maximum value
     maxValue = max(maxValue, val);
    }
}
 
// Print the calculated maximum value
cout<<"The maximum possible value is: "<<maxValue<<endl;
 
 }

Time Complexity 

In the above program to to find the  find the maximum value of a string generated by concatenating any substring of X with any substring of Y, the following steps have taken time:

1. Function call to find all the substrings of X - Time Complexity = O(N_x ^ 3)
2. Function call to find all the substrings of X - Time Complexity = O(N_Y ^ 3)

The function to find all the substrings of a string is taking cubic polynomial time complexity as three nested loops are used inside the function

1. For concatenating every substring of X with every substring of Y, two nested “for loops” are used - Time Complexity = O(Number of substrings of X * Number of substrings of Y).

Number of substrings of a string of length ‘n’ = (n*(n+1))/2

So, here time complexity of these two nested loops is O(N_x^2 * N_Y ^ 2)

Inside these two nested loops, the function “findValue()” is called. Inside the function a “for loop” is used inside which function “f()” is called. Inside the function “f()”, “findSubstrings()” function is called for ‘S’. The longest length of ‘S’ can be N_X + N_Y. So, the worst case time complexity for “findValue()” function will be O (N * ( ((N_X + N_Y) ^ 3) + ((N_X + N_Y) ^ 2)))

Thus the  time complexity = O(N_x ^ 3) +  O(N_Y ^ 3) + O((N_x^2 * N_Y ^ 2) * ((N * ( ((N_X + N_Y) ^ 3) + ((N_X + N_Y) ^ 2))))

= O(N_x ^ 3) +  O(N_Y ^ 3) + O((N_x^2 * N_Y ^ 2) * (N * ((N_X + N_Y) ^ 3))

Where N_X and N_Y are the length of strings X and Y respectively and N is the total number of strings that Ninja have.

Space Complexity 

In the above program to find the maximum value of a string generated by concatenating any substring of X with any substring of Y, we have created vectors to store the total number of substrings of X, Y and S which takes O(N_X ^ 2), O (N_Y ^ 2), and O((N_X + N_Y) ^ 2 ) space respectively. So, the overall space complexity is O((N_X + N_Y) ^ 2 ).