Given a binary string S and a string of non-zero digits P of length N, the task is to maximize the sum using the given operations, which can be used as my times you can:
- You can choose a substring of length 2 or 3.
- Delete that substring after calculating the absolute difference of adjacent elements from left to right and take any single digit from the string P and multiply that with the absolute difference obtained by chosen substring.
Examples:
Input: N = 4, S = 1001, P = 6574
Output: 13
Explanation: For string S = 1001, choose a substring from index 1 to 2 as substring= 10. Absolute difference = |1 – 0| = 1 Multiply it with the digit 7 of string P = 7*1 = 7. Now chosen substring (10) is deleted from string (1001) and remaining string is = 01.
Then, choose a substring from index 1 to 2 as substring = 01. Absolute difference = |0-1| = 1, Multiply it with the 6 of string P = 6*1 = 6. Now substring is deleted and string S is empty, and total maximum sum that can obtain is 7+6 = 13.Input: N = 4, S = 1111, P = 1221
Output: 2
Explanation: For, string S = 1111, choose a sub-array from index 1 to 3 as sub-array = 111. Absolute difference of first left two elements of chosen substring = |1-1| = 0, Now substring is = 01.(By replacing obtained abs. difference with first two elements).
Now, absolute difference of first left two elements of current sub-array (01) = |0-1| = 1. Total absolute difference for this substring is 1. Take digit 2 from P and multiply it with obtained absolute difference = 1*2= 2. Now delete this substring(111) from S(1111), Then remained S is = 1.
We cannot make any operations further, Because S has single element and have not any adjacent element. Therefore, Maximum sum that can obtain is = 2.
Approach: Implement the idea below to solve the problem:
The problem can be solved by using Stack data structure and greedy approach to choose a digit from string P for multiplication. For knowing the exact algorithm to solve the problem see the Algorithm section below.
Follow the steps to solve the problem:
- Initialize a Stack (say stk) and create a counter and sum variables.
- Make an ArrayList lets call it digits to store digits of string P and sort it.
- Run a loop from 1 to N and do
- If stk is empty or the top of stk = current_element, push the typecasted integer element in the stack.
- Else if top of stk is not the same as current_element, pop the peek element from stk and add (1*last element of digits) into sum variable also remove used digits from the list.
- Now it is possible that some element remained in the stack. Therefore, run a while loop till the stk has no element in it. Count the number of 1 remaining in the stk in the counter variable.
- Modify the counter variable’s value now with (counter/3). The reason is that 3 ones can make absolute difference as 1, same as the input 2 in the example above.
- Do the same, add (1*last element of digits ArrayList) into sum variable also remove used digits from the list, while counter is greater than 0.
- Print the value of the sum variable.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach.#include <bits/stdc++.h>using namespace std;// Function to find the maximum possible sumint maxSum(string S, string P, int N){ // List to store digits of string P vector<int> digits; // Loop for initializing digits of // string P into list for (int i = 0; i < P.length(); i++) { // Initializing digits by // typecasting it from string // to integer digits.push_back(P[i] - 48); // digits.add(Integer.parseInt("" + P.charAt(i))); } // Sorting digits of list so that // we can get max element at last // index each time using greedy // approach sort(digits.begin(), digits.end()); // digits.sort(null); int sum = 0; stack<int> s; // Loop for traversing on string for (int i = 0; i < N; i++) { // Creating current character // as string so that in-built // typecasted function can be // apply to below string str1 string str1 = ""; str1 += S[i]; // Typecasted value of string int typecasted_int = stoi(str1); // Condition when stack is empty if (s.empty()) { s.push(typecasted_int); } // Condition when peek element // of stack is equal to current // typecasted element else if (s.top() == typecasted_int) { s.push(typecasted_int); } // Condition when peek element // is not equal to current // typecasted element else if (s.top() != typecasted_int) { sum += digits.back(); // Removing used digit from list digits.pop_back(); s.pop(); } } int counter = 0; // While loop will run till the // stack is not empty while (!s.empty()) { // If peek element found // to be equal to 1 if (s.top() == 1) { counter++; } s.pop(); } // Three 111 can make abs // difference 1 Therefore total // number of 1 are divided by 3. counter = counter / 3; // Adding (abs diff.)*digit by // getting abs difference from // counter variable while (counter-- > 0) { sum += digits.back(); // Removing used digit from list digits.pop_back(); } return sum;}// Driver codeint main(){ string S = "1001"; string P = "6574"; int N = S.size(); // Function call cout << (maxSum(S, P, N));}// This code is contributed by garg28harsh. |
Java
// Java code to implement the approach.import java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to find the maximum possible sum static long maxSum(String S, String P, int N) { // List to store digits of string P ArrayList<Integer> digits = new ArrayList<>(); // Loop for initializing digits of // string P into list for (int i = 0; i < P.length(); i++) { // Initializing digits by // typecasting it from string // to integer digits.add(Integer.parseInt("" + P.charAt(i))); } // Sorting digits of list so that // we can get max element at last // index each time using greedy // approach digits.sort(null); long sum = 0; Stack<Integer> s = new Stack<>(); // Loop for traversing on string for (int i = 0; i < N; i++) { // Creating current character // as string so that in-built // typecasted function can be // apply to below string str1 String str1 = "" + S.charAt(i); // Typecasted value of string Integer typecasted_int = Integer.parseInt(str1); // Condition when stack is empty if (s.isEmpty()) { s.push(typecasted_int); } // Condition when peek element // of stack is equal to current // typecasted element else if (s.peek() == typecasted_int) { s.push(typecasted_int); } // Condition when peek element // is not equal to current // typecasted element else if (s.peek() != typecasted_int) { sum += 1 * (int)(digits.get(digits.size() - 1)); // Removing used digit from list digits.remove( digits.get(digits.size() - 1)); s.pop(); } } int counter = 0; // While loop will run till the // stack is not empty while (!s.isEmpty()) { // If peek element found // to be equal to 1 if (s.peek() == 1) { counter++; } s.pop(); } // Three 111 can make abs // difference 1 Therefore total // number of 1 are divided by 3. counter = counter / 3; // Adding (abs diff.)*digit by // getting abs difference from // counter variable while (counter-- > 0) { sum += 1 * digits.get(digits.size() - 1); // Removing used digit from list digits.remove(digits.get(digits.size() - 1)); } return sum; } // Driver code public static void main(String args[]) { String S = "1001"; String P = "6574"; int N = S.length(); // Function call System.out.println(maxSum(S, P, N)); }} |
Python
from typing import List# Function to find the maximum possible sumdef maxSum(S, P, N): # List to store digits of string P digits = [] # Loop for initializing digits of # string P into list for i in range(len(P)): # Initializing digits by # typecasting it from string to integer digits.append(int(P[i])) # Sorting digits of list so that # we can get max element at last # index each time using greedy # approach digits.sort() sum = 0 s = [] # Loop for traversing on string for i in range(N): # Creating current character # as string so that in-built # typecasted function can be # apply to below string str1 typecasted_int = int(S[i]) # Condition when stack is empty if not s: s.append(typecasted_int) # Condition when peek element # of stack is equal to current # typecasted element elif s[-1] == typecasted_int: s.append(typecasted_int) # Condition when peek element # is not equal to current # typecasted element elif s[-1] != typecasted_int: sum += digits[-1] # Removing used digit from list del digits[-1] del s[-1] counter = 0 # While loop will run till the # stack is not empty while s: # If peek element found # to be equal to 1 if s[-1] == 1: counter += 1 del s[-1] # Three 111 can make abs # difference 1 Therefore total # number of 1 are divided by 3. counter = counter // 3 # Adding (abs diff.)*digit by # getting abs difference from # counter variable while counter > 0: sum += digits[-1] # Removing used digit from list del digits[-1] counter -= 1 return sum# Driver codeif __name__ == "__main__": S = "1001" P = "6574" N = len(S) # Function call print(maxSum(S, P, N)) |
C#
// C# code to implement the approach.using System;using System.Collections;using System.Collections.Generic;public class GFG { // Function to find the maximum possible sum static long maxSum(string S, string P, int N) { // List to store digits of string P ArrayList digits = new ArrayList(); // Loop for initializing digits of // string P into list for (int i = 0; i < P.Length; i++) { // Initializing digits by // typecasting it from string // to integer digits.Add(int.Parse("" + P[i])); } // Sorting digits of list so that // we can get max element at last // index each time using greedy // approach digits.Sort(null); long sum = 0; Stack s = new Stack(); // Loop for traversing on string for (int i = 0; i < N; i++) { // Creating current character // as string so that in-built // typecasted function can be // apply to below string str1 string str1 = "" + S[i]; // Typecasted value of string int typecasted_int = int.Parse(str1); // Condition when stack is empty if (s.Count == 0) { s.Push(typecasted_int); } // Condition when peek element // of stack is equal to current // typecasted element else if ((int)s.Peek() == typecasted_int) { s.Push(typecasted_int); } // Condition when peek element // is not equal to current // typecasted element else if ((int)s.Peek() != typecasted_int) { sum += 1 * (int)(digits[digits.Count - 1]); // Removing used digit from list digits.Remove(digits[digits.Count - 1]); s.Pop(); } } int counter = 0; // While loop will run till the // stack is not empty while (s.Count != 0) { // If peek element found // to be equal to 1 if ((int)s.Peek() == 1) { counter++; } s.Pop(); } // Three 111 can make abs // difference 1 Therefore total // number of 1 are divided by 3. counter = counter / 3; // Adding (abs diff.)*digit by // getting abs difference from // counter variable while (counter-- > 0) { sum += 1 * (int)digits[digits.Count - 1]; // Removing used digit from list digits.Remove(digits[digits.Count - 1]); } return sum; } static public void Main() { // Code string S = "1001"; string P = "6574"; int N = S.Length; // Function call Console.WriteLine(maxSum(S, P, N)); }}// This code is contributed by lokesh. |
Javascript
// Javascript code to implement the approach.// Function to find the maximum possible sumfunction maxSum(S, P, N) { // List to store digits of string P let digits = []; // Loop for initializing digits of // string P into list for (let i = 0; i < P.length; i++) { // Initializing digits by // typecasting it from string // to integer digits.push(parseInt("" + P[i])); } // Sorting digits of list so that // we can get max element at last // index each time using greedy // approach digits.sort(); let sum = 0; let s = []; // Loop for traversing on string for (let i = 0; i < N; i++) { // Creating current character // as string so that in-built // typecasted function can be // apply to below string str1 let str1 = "" + S[i]; // Typecasted value of string let typecasted_int = parseInt(str1); // Condition when stack is empty if (s.length == 0) { s.push(typecasted_int); } // Condition when peek element // of stack is equal to current // typecasted element else if (s[S.length - 1] == typecasted_int) { s.push(typecasted_int); } // Condition when peek element // is not equal to current // typecasted element else if (s[s.length - 1] != typecasted_int) { sum += 1 * parseInt(digits[digits.length - 1]); // Removing used digit from list digits.pop(); s.pop(); } } let counter = 0; // While loop will run till the // stack is not empty while (s.length != 0) { // If peek element found // to be equal to 1 if (s[S.length - 1] == 1) { counter++; } s.pop(); } // Three 111 can make abs // difference 1 Therefore total // number of 1 are divided by 3. counter = counter / 3; // Adding (abs diff.)*digit by // getting abs difference from // counter variable while (counter-- > 0) { sum += 1 * digits[digits.length - 1]; // Removing used digit from list digits.pop(); } return sum;}// Driver codelet S = "1001";let P = "6574";let N = S.length;// Function callconsole.log(maxSum(S, P, N));// This code is contributed by ksam24000 |
Output
13
Time Complexity: O(N * log(N)), because sorting is performed.
Auxiliary Space: O(N), as list is required to store digits.
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!
Share your thoughts in the comments
