Genere una string a partir de las strings P y Q dadas en función de las condiciones dadas

Dadas dos strings P y Q, la tarea es generar una string S que satisfaga las siguientes condiciones: 

• Encuentre S tal que P esté reordenado y Q sea una substring en él.
• Todos los caracteres antes de Q en S deben ser menores o iguales que el primer carácter en Q y en orden lexicográfico.
• El resto de los caracteres deben estar presentes después de la Q en orden lexicográfico.

Nota: Todos los caracteres de Q siempre están presentes en P y la longitud de Q siempre es menor o igual que la longitud de P.

Ejemplos:

Entrada: P = “geeksforgeeksfor” Q = “for”
Salida: eeeeffforgkkorss
Explicación: 
Los caracteres ‘e’ y ‘f’ son los únicos caracteres aquí que son menores o iguales que ‘f’ (primer carácter de Q). 
Entonces, antes de “for” la string es lexicográficamente igual a eeeef. El resto de los caracteres de P son mayores que ‘f’, por lo que se colocan después de “for” en orden lexicográfico. Así, después de “for”, la string es ggkkorss. Por lo tanto, la salida es eeefforggkkorss. 

Entrada: P = “lexicográfico” Q = “brecha”
Salida: accegaphiillorx
Explicación: 
La string accegaphiillorx satisface las condiciones anteriores para las strings P y Q.

Planteamiento: La idea es encontrar las frecuencias de todos los caracteres en P y Q para resolver el problema. 

• Mantenga una array de frecuencias de todos los alfabetos en P y Q.
• Después de encontrar las frecuencias, separe los caracteres en P de acuerdo con el primer carácter en Q y agréguelos a la string resultante.
• Devuelve la string resultante al final.

A continuación se muestra la implementación del enfoque anterior:

// 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 conditions
void 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 Code
int main()
{
    string P = "geeksforgeeksfor";
    string Q = "for";
     
    // Function call
    manipulateStrings(P, Q);
}
 
// This code is contributed by Amit Katiyar

// Java Program to implement
// the above approach
import java.util.*;
import java.lang.*;
import java.io.*;
 
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 = "geeksforgeeksfor";
        String Q = "for";
        // Function call
        manipulateStrings(P, Q);
    }
}

# Python3 program to implement
# the above approach
 
# Function to generate a string S
# from string P and Q according to
# the given conditions
def 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 Code
if __name__=="__main__":
     
    P = "geeksforgeeksfor";
    Q = "for";
      
    # Function call
    manipulateStrings(P, Q);
 
# This code is contributed by rutvik_56

// C# Program to implement
// the above approach
using 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 = "geeksforgeeksfor";
    String Q = "for";
     
    // Function call
    manipulateStrings(P, Q);
  }
}
 
// This code is contributed by Rohit_ranjan

<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 = "geeksforgeeksfor";
      var Q = "for";
 
      // Function call
      manipulateStrings(P, Q);
       
</script>

eeeefforggkkorss

Complejidad temporal: O(N+M) donde N y M son las longitudes respectivas de P y Q. 
Espacio auxiliar: O(1)