Given an array of strings and an array of integers where ith integer of the array corresponds to the value of the ith string present in the string array. Now pick two strings that have the smallest values in the integer array and sum up both the integers and concatenate the strings and add both the summed up integer to the integer array and the concatenated string to the string array, and keep repeating the whole process until only a single element is left in both the arrays. Also, note that once any two strings and integers are picked they get deleted from the array and new strings and integers are added back to the respective arrays.
The task is to print the final string obtained.
Examples:
Input: str = {“Geeks”, “For”, “Geeks”}, num = {2, 3, 7}
Output: GeeksForGeeks
Pick 2 and 3 add them, and form “GeeksFor” and 5
Add them back to the arrays, str = {“GeeksFor”, “Geeks”}, num = {5, 7}
Now pick 7 and 5 add them to form “GeeksForGeeks” which is the final string.Input: str = {“abc”, “def”, “ghi”, “jkl”}, num = {1, 4, 2, 6}
Output: jklabcghidef
Approach: The idea is to use a priority queue, and make a pair of strings and their corresponding values and store them in the priority queue and keep dequeuing two pairs from the priority queue, adding the integers and concatenating the strings, and enqueuing them back into the priority queue, till the size of the queue reduces to one, and then print the only remaining string in the queue.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Class that represents a pairstruct Priority{ string s; int count;};struct Compare { int operator()(Priority a, Priority b) { if (a.count > b.count) return 1; else if (a.count < b.count) return -1; return 0; }};// Function that prints the final stringstatic void FindString(string str[], int num[], int n){ priority_queue<int, vector<Priority>, Compare> p; // Add all the strings and their corresponding // values to the priority queue for(int i = 0; i < n; i++) { Priority x; x.s = str[i]; x.count = num[i]; p.push(x); } // Take those two strings from the priority // queue whose corresponding integer values // are smaller and add them up as well as // their values and add them back to the // priority queue while there are more // than a single element in the queue while (p.size() > 1) { // Get the minimum valued string Priority x = p.top(); p.pop(); // p.remove(x); // Get the second minimum valued string Priority y = p.top(); p.pop(); // Updated integer value int temp = x.count + y.count; string sb = x.s + y.s; // Create new entry for the queue Priority z; z.count = temp; z.s = sb; // Add to the queue p.push(z); } // Print the only remaining string Priority z = p.top(); p.pop(); cout << z.s << endl;}// Driver codeint main() { string str[] = { "Geeks", "For", "Geeks" }; int num[] = { 2, 3, 7 }; int n = sizeof(num) / sizeof(int); FindString(str, num, n);}// This code is contributed by sanjeev2552 |
Java
// Java implementation of the approachimport java.util.*;import java.lang.*;// Class that represents a pairclass Priority { String s; int count;}class PQ implements Comparator<Priority> { public int compare(Priority a, Priority b) { if (a.count > b.count) return 1; else if (a.count < b.count) return -1; return 0; }}class GFG { // Function that prints the final string static void FindString(String str[], int num[], int n) { Comparator<Priority> comparator = new PQ(); PriorityQueue<Priority> p = new PriorityQueue<Priority>(comparator); // Add all the strings and their corresponding // values to the priority queue for (int i = 0; i < n; i++) { Priority x = new Priority(); x.s = str[i]; x.count = num[i]; p.add(x); } // Take those two strings from the priority // queue whose corresponding integer values are smaller // and add them up as well as their values and // add them back to the priority queue // while there are more than a single element in the queue while (p.size() > 1) { // Get the minimum valued string Priority x = p.poll(); p.remove(x); // Get the second minimum valued string Priority y = p.poll(); p.remove(y); // Updated integer value int temp = x.count + y.count; String sb = x.s + y.s; // Create new entry for the queue Priority z = new Priority(); z.count = temp; z.s = sb; // Add to the queue p.add(z); } // Print the only remaining string Priority z = p.poll(); System.out.println(z.s); } // Driver code public static void main(String[] args) { String str[] = { "Geeks", "For", "Geeks" }; int num[] = { 2, 3, 7 }; int n = num.length; FindString(str, num, n); }} |
Python3
# Python program for the above approach# Function that prints the final stringdef FindString(str, num, n): p = [] # Add all the strings and their corresponding # values to the priority queue for i in range(n): x = [0,0] x[0] = str[i] x[1] = num[i] p.append(x) # Take those two strings from the priority # queue whose corresponding integer values # are smaller and add them up as well as # their values and add them back to the # priority queue while there are more # than a single element in the queue while (len(p) > 1): # Get the minimum valued string x = p[-1] p.pop() # p.remove(x); # Get the second minimum valued string y = p[-1] p.pop() # Updated integer value temp = x[1] + y[1] sb = x[0] + y[0] # Create new entry for the queue z = [0,0] z[1] = temp z[0] = sb # Add to the queue p.append(z) # Print the only remaining string z = p[-1] p.pop() print(z[0])# Driver codestr = ["Geeks", "For", "Geeks"]num = [2, 3, 7]n = len(num)FindString(str, num, n);# This code is contributed by shinjanpatra |
Javascript
<script>// Javascript implementation of the approach// Function that prints the final stringfunction FindString(str, num, n){ var p = []; // Add all the strings and their corresponding // values to the priority queue for(var i = 0; i < n; i++) { var x = [0,0]; x[0] = str[i]; x[1] = num[i]; p.push(x); } // Take those two strings from the priority // queue whose corresponding integer values // are smaller and add them up as well as // their values and add them back to the // priority queue while there are more // than a single element in the queue while (p.length > 1) { // Get the minimum valued string var x = p[p.length-1]; p.pop(); // p.remove(x); // Get the second minimum valued string var y = p[p.length-1]; p.pop(); // Updated integer value var temp = x[1] + y[1]; var sb = x[0] + y[0]; // Create new entry for the queue var z = [0,0]; z[1] = temp; z[0] = sb; // Add to the queue p.push(z); } // Print the only remaining string var z = p[p.length-1]; p.pop(); document.write(z[0] + "<br>");}// Driver codevar str = ["Geeks", "For", "Geeks"];var num = [2, 3, 7];var n = num.length;FindString(str, num, n);// This code is contributed by rutvik_56.</script> |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class Program{ // Function that prints the final string static void FindString(string[] str, int[] num, int n) { var p = new List<Tuple<string, int>>(); // Add all the strings and their corresponding // values to the priority queue for (int i = 0; i < n; i++) { var x = new Tuple<string, int>(str[i], num[i]); p.Add(x); } // Take those two strings from the priority // queue whose corresponding integer values // are smaller and add them up as well as // their values and add them back to the // priority queue while there are more // than a single element in the queue while (p.Count > 1) { // Get the minimum valued string var x = p[p.Count - 1]; p.RemoveAt(p.Count - 1); // Get the second minimum valued string var y = p[p.Count - 1]; p.RemoveAt(p.Count - 1); // Updated integer value var temp = x.Item2 + y.Item2; var sb = x.Item1 + y.Item1; // Create new entry for the queue var z = new Tuple<string, int>(sb, temp); // Add to the queue p.Add(z); } // Print the only remaining string var z1 = p[p.Count - 1]; p.RemoveAt(p.Count - 1); Console.WriteLine(z1.Item1); } // Driver code static void Main(string[] args) { string[] str = { "Geeks", "For", "Geeks" }; int[] num = { 2, 3, 7 }; int n = num.Length; FindString(str, num, n); // This code is contributed by princekumaras }} |
Output:
GeeksForGeeks
Time Complexity: O(N * log(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!
