Given an array of string S[] of size N, the task is to find the maximum size of the resultant string formed by adding some strings and following the given condition that If a string of size K is chosen to add in the resultant string then the next K/2 strings cannot be selected to be a part of the resultant array.
Examples:
Input: S[] = {“well”, “do”, “hi”, “by”}
Output: 6
Explanation: Choose “well” and skip “do” and “hi”(sizeof(“well”)/2) and then choose “by”. So, size will be 6.Input: s[] = {“neveropen”, “for”, “neveropen”, “is”, “best”}
Output: 9
Approach: This problem can be solved using memoization. Follow the steps below:
- For each string S[i], there are two options i.e. to choose the current string or not.
- So if the string is chosen, its length, say K will contribute to the length of the resultant array and now, only the strings after K/2 can be chosen.
- Now if the string is excluded, just move further.
- Print the answer according to the above observation
Below is the implementation of the above approach
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Recursive function to find the// maximum length of the resultant stringint maxsum(string S[], int N, int i, vector<int>& dp){ // If index gets out of bound return 0 if (i >= N) return 0; // If value not already computed // then compute it if (dp[i] == -1) { // To include the current string int op1 = S[i].size() + maxsum(S, N, (i + S[i].size() / 2) + 1, dp); // To exclude the current string int op2 = maxsum(S, N, i + 1, dp); // Maximum of both the options dp[i] = max(op1, op2); } return dp[i];}// Driver Codeint main(){ string S[] = { "neveropen", "for", "neveropen", "is", "best" }; int N = sizeof(S) / sizeof(S[0]); vector<int> dp(N, -1); cout << maxsum(S, N, 0, dp); return 0;} |
Java
// Java implementation of the above approachimport java.util.Arrays;class GFG { // Recursive function to find the // maximum length of the resultant string static int maxsum(String S[], int N, int i, int[] dp) { // If index gets out of bound return 0 if (i >= N) return 0; // If value not already computed // then compute it if (dp[i] == -1) { // To include the current string int op1 = S[i].length() + maxsum(S, N, (i + S[i].length() / 2) + 1, dp); // To exclude the current string int op2 = maxsum(S, N, i + 1, dp); // Maximum of both the options dp[i] = Math.max(op1, op2); } return dp[i]; } // Driver Code public static void main(String args[]) { String S[] = { "neveropen", "for", "neveropen", "is", "best" }; int N = S.length; int[] dp = new int[N]; Arrays.fill(dp, -1); System.out.println(maxsum(S, N, 0, dp)); }}// This code is contributed by saurabh_jaiswal. |
Python3
# Python implementation of the above approach# Recursive function to find the# maximum length of the resultant stringdef maxsum(S, N, i, dp): # If index gets out of bound return 0 if (i >= N): return 0 # If value not already computed # then compute it if (dp[i] == -1): # To include the current string op1 = int(len(S[i]) + maxsum(S, N, (i + len(S[i]) // 2)+1, dp)) # To exclude the current string op2 = int(maxsum(S, N, i + 1, dp)) # Maximum of both the options dp[i] = max(op1, op2) return dp[i]# Driver CodeS = ["neveropen", "for", "neveropen", "is", "best"]N = len(S)dp = []for i in range(0, N): dp.append(-1)print(maxsum(S, N, 0, dp))# This code is contributed by Taranpreet |
C#
// C# implementation of the above approachusing System;public class GFG{ // Recursive function to find the // maximum length of the resultant string static int maxsum(String []S, int N, int i, int[] dp) { // If index gets out of bound return 0 if (i >= N) return 0; // If value not already computed // then compute it if (dp[i] == -1) { // To include the current string int op1 = S[i].Length + maxsum(S, N, (i + S[i].Length / 2) + 1, dp); // To exclude the current string int op2 = maxsum(S, N, i + 1, dp); // Maximum of both the options dp[i] = Math.Max(op1, op2); } return dp[i]; } // Driver Code public static void Main(String []args) { String []S = { "neveropen", "for", "neveropen", "is", "best" }; int N = S.Length; int[] dp = new int[N]; for(int i = 0;i<N;i++) dp[i] = -1; Console.WriteLine(maxsum(S, N, 0, dp)); }}// This code is contributed by umadevi9616 |
Javascript
<script> // JavaScript code for the above approach // Recursive function to find the // maximum length of the resultant string function maxsum(S, N, i, dp) { // If index gets out of bound return 0 if (i >= N) return 0; // If value not already computed // then compute it if (dp[i] == -1) { // To include the current string let op1 = S[i].length + maxsum(S, N, (i + Math.floor(S[i].length / 2)) + 1, dp); // To exclude the current string let op2 = maxsum(S, N, i + 1, dp); // Maximum of both the options dp[i] = Math.max(op1, op2); } return dp[i]; } // Driver Code let S = ["neveropen", "for", "neveropen", "is", "best"]; let N = S.length; let dp = new Array(N).fill(-1) document.write(maxsum(S, N, 0, dp)); // This code is contributed by Potta Lokesh </script> |
Output:
9
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a vector to store the solution of the subproblems.
- Initialize the table with base cases
- Fill up the table iteratively
- Return the final solution
Implementation :
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Iterative function to find the// maximum length of the resultant stringint maxsum(string S[], int N){ // create vector to store the computations of // subproblems vector<int> dp(N + 1); dp[N] = 0; // base case // loop to compute the bigger values for (int i = N - 1; i >= 0; i--) { int op1 = S[i].size() + dp[i + S[i].size() / 2 + 1]; int op2 = dp[i + 1]; // store answer of subproblem dp[i] = max(op1, op2); } // return answer return dp[0];}// Driver codeint main(){ string S[] = { "neveropen", "for", "neveropen", "is", "best" }; int N = sizeof(S) / sizeof(S[0]); cout << maxsum(S, N) << endl; return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;class Main { // Iterative function to find the maximum length of the // resultant string static int maxsum(String S[], int N) { // create array to store the computations of // subproblems int[] dp = new int[N + 1]; dp[N] = 0; // base case // loop to compute the bigger values for (int i = N - 1; i >= 0; i--) { int j = i + S[i].length() / 2 + 1; int op1 = j < N ? S[i].length() + dp[j] : S[i].length(); int op2 = dp[i + 1]; // store answer of subproblem dp[i] = Math.max(op1, op2); } // return answer return dp[0]; } // Driver code public static void main(String[] args) { String S[] = { "neveropen", "for", "neveropen", "is", "best" }; int N = S.length; System.out.println(maxsum(S, N)); }} |
Python3
def maxsum(S, N): # create list to store the computations of subproblems dp = [0] * (N + 1) dp[N] = 0 # base case # loop to compute the bigger values for i in range(N - 1, -1, -1): op1 = len(S[i]) + dp[min(i + len(S[i]) // 2 + 1, N)] op2 = dp[i + 1] # store answer of subproblem dp[i] = max(op1, op2) # return answer return dp[0]# Driver codeS = ["neveropen", "for", "neveropen", "is", "best"]N = len(S)print(maxsum(S, N)) |
C#
// C# program for above approachusing System;using System.Linq;using System.Collections.Generic;public class Program { // Iterative function to find the // maximum length of the resultant string public static int MaxSum(string[] S, int N) { // create list to store the computations of // subproblems List<int> dp = new List<int>(new int[N + 1]); dp[N] = 0; // base case // loop to compute the bigger values for (int i = N - 1; i >= 0; i--) { int op1 = S[i].Length + (i + S[i].Length / 2 + 1 <= N ? dp[i + S[i].Length / 2 + 1] : 0); int op2 = dp[i + 1]; // store answer of subproblem dp[i] = Math.Max(op1, op2); } // return answer return dp[0]; } // Driver code public static void Main() { string[] S = { "neveropen", "for", "neveropen", "is", "best" }; int N = S.Length; Console.WriteLine(MaxSum(S, N)); }}// this code is contributed by chetanbargal |
Javascript
function maxsum(S, N) { // create array to store the computations of subproblems let dp = new Array(N + 1).fill(0); dp[N] = 0; // base case // loop to compute the bigger values for (let i = N - 1; i >= 0; i--) { let op1 = S[i].length + dp[Math.min(i + Math.floor(S[i].length / 2) + 1, N)]; let op2 = dp[i + 1]; // store answer of subproblem dp[i] = Math.max(op1, op2); } // return answer return dp[0];}// Driver codelet S = ["neveropen", "for", "neveropen", "is", "best"];let N = S.length;console.log(maxsum(S, N));// This code is contributed by user_dtewbxkn77n |
Output :
9
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
