Given two strings P and Q, the task is to generate a string S satisfying the following conditions:
- Find S such that P is rearranged and Q is a substring in it.
- All the characters before Q in S should be smaller than or equal to the first character in Q and in lexicographic order.
- The rest of the characters should be present after Q in lexicographic order
Note: All characters of Q are always present in P and length of Q is always less than or equal to the length of P.
Examples:
Input : P = “neveropenfor” Q = “for”
Output : eeeefforggkkorss
Explanation:
The characters ‘e’ and ‘f’ are the only characters here which are less than or equal to ‘f’ (first character of Q).
So, before “for” the string is lexicographically equal to eeeef.
The rest of the characters in P are greater than ‘f’, so they are placed after “for” in lexicographic order.
Thus, after “for”, the string is ggkkorss.
Therefore the output is eeeefforggkkorss.Input : P = “lexicographical” Q = “gap”
Output : accegaphiillorx
Explanation:
The string accegaphiillorx satisfies the above conditions for string P and Q.
Approach: The idea is to find the frequencies of all the characters in P and Q to solve the problem.
- Maintain an array of frequencies of all the alphabets in P and Q.
- After finding the frequencies, segregate the characters in P according to the first character in Q and add them to the resulting string.
- Return the resulting string at the end.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to generate a string S from string P// and Q according to the given conditionsvoid manipulateStrings(string P, string Q){ // Stores the frequencies int freq[26]; memset(freq, 0, sizeof(freq)); // Counts occurrences of each characters for (int i = 0; i < P.size(); i++) { freq[P[i] - 'a']++; } // Reduce the count of the character // which is also present in Q for (int i = 0; i < Q.size(); i++) { freq[Q[i] - 'a']--; } // Stores the resultant string string sb = ""; // Index in freq[] to segregate the string int pos = Q[0] - 'a'; for (int i = 0; i <= pos; i++) { while (freq[i] > 0) { char c = (char)('a' + i); sb += c; freq[i]--; } } // Add Q to the resulting string sb += Q; for (int i = pos + 1; i < 26; i++) { while (freq[i] > 0) { char c = (char)('a' + i); sb += c; freq[i]--; } } cout << sb << endl;}// Driver Codeint main(){ string P = "neveropenfor"; string Q = "for"; // Function call manipulateStrings(P, Q);}// This code is contributed by Amit Katiyar |
Java
// Java Program to implement// the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to generate a string S from string P // and Q according to the given conditions public static void manipulateStrings(String P, String Q) { // Stores the frequencies int[] freq = new int[26]; // Counts occurrences of each characters for (int i = 0; i < P.length(); i++) { freq[P.charAt(i) - 'a']++; } // Reduce the count of the character // which is also present in Q for (int i = 0; i < Q.length(); i++) { freq[Q.charAt(i) - 'a']--; } // Stores the resultant string StringBuilder sb = new StringBuilder(); // Index in freq[] to segregate the string int pos = Q.charAt(0) - 'a'; for (int i = 0; i <= pos; i++) { while (freq[i] > 0) { char c = (char)('a' + i); sb.append(c); freq[i]--; } } // Add Q to the resulting string sb.append(Q); for (int i = pos + 1; i < 26; i++) { while (freq[i] > 0) { char c = (char)('a' + i); sb.append(c); freq[i]--; } } System.out.println(sb); } // Driver Code public static void main(String[] args) { String P = "neveropenfor"; String Q = "for"; // Function call manipulateStrings(P, Q); }} |
Python3
# Python3 program to implement# the above approach# Function to generate a string S# from string P and Q according to# the given conditionsdef manipulateStrings(P, Q): # Stores the frequencies freq = [0 for i in range(26)] # Counts occurrences of each characters for i in range(len(P)): freq[ord(P[i]) - ord('a')] += 1 # Reduce the count of the character # which is also present in Q for i in range(len(Q)): freq[ord(Q[i]) - ord('a')] -= 1 # Stores the resultant string sb = "" # Index in freq[] to segregate the string pos = ord(Q[0]) - ord('a') for i in range(pos + 1): while freq[i] > 0: sb += chr(ord('a') + i) freq[i] -= 1 # Add Q to the resulting string sb += Q for i in range(pos + 1, 26): while freq[i] > 0: sb += chr(ord('a') + i) freq[i] -= 1 print(sb)# Driver Codeif __name__ == "__main__": P = "neveropenfor" Q = "for" # Function call manipulateStrings(P, Q)# This code is contributed by rutvik_56 |
C#
// C# Program to implement// the above approachusing System;class GFG { // Function to generate a string S from string P // and Q according to the given conditions public static void manipulateStrings(String P, String Q) { // Stores the frequencies int[] freq = new int[26]; // Counts occurrences of each characters for (int i = 0; i < P.Length; i++) { freq[P[i] - 'a']++; } // Reduce the count of the character // which is also present in Q for (int i = 0; i < Q.Length; i++) { freq[Q[i] - 'a']--; } // Stores the resultant string String sb = ""; // Index in []freq to segregate the string int pos = Q[0] - 'a'; for (int i = 0; i <= pos; i++) { while (freq[i] > 0) { char c = (char)('a' + i); sb += c; freq[i]--; } } // Add Q to the resulting string sb += Q; for (int i = pos + 1; i < 26; i++) { while (freq[i] > 0) { char c = (char)('a' + i); sb += c; freq[i]--; } } Console.WriteLine(sb); } // Driver Code public static void Main(String[] args) { String P = "neveropenfor"; String Q = "for"; // Function call manipulateStrings(P, Q); }}// This code is contributed by Rohit_ranjan |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to generate a string S from string P // and Q according to the given conditions function manipulateStrings(P, Q) { // Stores the frequencies var freq = new Array(26).fill(0); // Counts occurrences of each characters for (var i = 0; i < P.length; i++) { freq[P[i].charCodeAt(0) - "a".charCodeAt(0)]++; } // Reduce the count of the character // which is also present in Q for (var i = 0; i < Q.length; i++) { freq[Q[i].charCodeAt(0) - "a".charCodeAt(0)]--; } // Stores the resultant string var sb = ""; // Index in []freq to segregate the string var pos = Q[0].charCodeAt(0) - "a".charCodeAt(0); for (var i = 0; i <= pos; i++) { while (freq[i] > 0) { var c = String.fromCharCode("a".charCodeAt(0) + i); sb += c; freq[i]--; } } // Add Q to the resulting string sb += Q; for (var i = pos + 1; i < 26; i++) { while (freq[i] > 0) { var c = String.fromCharCode("a".charCodeAt(0) + i); sb += c; freq[i]--; } } document.write(sb); } // Driver Code var P = "neveropenfor"; var Q = "for"; // Function call manipulateStrings(P, Q); </script> |
Output
eeeefforggkkorss
Time Complexity: O(N+M) where N and M are the respective lengths of P and Q.
Auxiliary Space: O(N), using extra space for string sb.
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!
