String lexicográficamente más grande formada al elegir palabras de una oración dada según un patrón dado

Dada una oración S y una string B que tienen caracteres distintos, encuentre una string uniendo las palabras de S de acuerdo con las condiciones dadas:

• Elige una palabra de S si
  • Tiene al menos longitud (B)/2 caracteres de la string B o
  • Tener al menos un carácter de la string B y ordenado lexicográficamente en orden creciente.
• La string formada debe ser lexicográficamente la string más grande.

Ejemplos:

Entrada: S = «peek geek suv», B = «ekps»
Salida: suvpeekgeek
Explicación: « suv» tiene un carácter de B y está ordenado en orden creciente.
Mientras que «peek» y «geek» tienen una longitud (B)/2 caracteres.

Entrada: S = “peek fit and run”, B = “ekta”
Salida: peekfit  

Enfoque ingenuo : la tarea se puede resolver almacenando tanto la palabra de la string S como la string B en un conjunto y comparando si son iguales, pero esto requeriría más de un conjunto, lo que requiere tiempo y espacio adicionales.

Complejidad de tiempo: O(N * logN) donde N es el número total de caracteres en S
Espacio auxiliar: O(N)

Enfoque eficiente: el mejor enfoque es utilizar un mapa . Siguiendo los pasos que se mencionan a continuación:

• Almacene la frecuencia de los caracteres de B en un mapa desordenado y compárela con las strings de la array S .
• Si existen dos caracteres en una palabra de la string S  , agréguelos a la string de salida.
• Si solo hay un carácter presente, verifique si está ordenado en orden lexicográfico creciente.
• En caso afirmativo, agréguelo a la string de salida.
• Organice la string de salida en la permutación lexicográficamente más grande.

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

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Check if sorted or not
bool isosrted(string s)
{
    for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] > s[i + 1])
            return false;
    }
    return true;
}
 
// Function to get the lexicographically largest string
string choosestr(string s, string b, int n)
{
    unordered_map<char, int> m;
    set<string, greater<string> > ss;
 
    // Count frequencies of characters
    for (int i = 0; b[i]; i++) {
        m[b[i]]++;
    }
    int g = b.size() / 2;
    int c = 0;
    string k = "", p;
    stringstream sg(s);
 
    // Traverse through sentence
    while (sg >> p) {
        c = 0;
        for (int j = 0; j < p.size(); j++) {
            if (m[p[j]])
                c++;
            if (c == g)
                break;
        }
 
        // Store the output according
        // to the given conditions
        if ((c == 1 and isosrted(p)) or c == g)
            ss.insert(p);
    }
 
    // Lexicographically largest string
    for (auto i : ss) {
        k += i;
    }
    return k;
}
 
// Driver code
int main()
{
    string S = "peek fit and run";
    string B = "ekta";
    int N = sizeof(S) / sizeof(S[0]);
    cout << choosestr(S, B, N);
    return 0;
}

# Python program for the above approach:
 
## Check if sorted or not
def isosrted(s):
    for i in range(len(s)-1):
        if (s[i] > s[i + 1]):
            return False
    return True
 
## Function to get the lexicographically largest string
def choosestr(s, b, n):
    m = {};
    ss =set({})
 
    ## Count frequencies of characters
    for i in range(len(b)):
        if (b[i] in m):
            m[b[i]]+=1
        else:
            m[b[i]] = 1
     
    g = len(b) // 2
    c = 0
    k = "";
    arr = s.split(" ");
 
    ## Traverse through sentence
    for p in arr:
        c = 0
        for j in range(len(p)):
            if (p[j] in m):
                c+=1
            if (c == g):
                break
 
        ## Store the output according
        ## to the given conditions
        if ((c == 1 and isosrted(p)) or c == g):
            ss.add(p)
 
    ans = []
    for i in ss:
        ans.append(i)
    ans.sort()
    ans.reverse()
 
    ## Lexicographically largest string
    for i in ans:
        k += i
    return k
 
## Driver code
if __name__ == '__main__':
    S = "peek fit and run"
    B = "ekta"
    N = len(S)
    print(choosestr(S, B, N))
     
    # This code is contributed by subhamgoyal2014.

<script>
    // JavaScript code for the above approach
 
    // Check if sorted or not
    const isosrted = (s) => {
        for (let i = 0; i < s.length - 1; i++) {
            if (s[i] > s[i + 1])
                return false;
        }
        return true;
    }
 
    // Function to get the lexicographically largest string
    const choosestr = (s, b, n) => {
        let m = {};
        let ss = new Set();
 
        // Count frequencies of characters
        for (let i = 0; i < b.length; i++) {
            if (b[i] in m) m[b[i]]++;
            else m[b[i]] = 1;
        }
        let g = parseInt(b.length / 2);
        let c = 0;
        let k = "";
        let p = s.split(" ");
 
        // Traverse through sentence
        for (let i in p) {
            c = 0;
            for (let j = 0; j < p[i].length; j++) {
                if (p[i][j] in m)
                    c++;
                if (c == g)
                    break;
            }
 
            // Store the output according
            // to the given conditions
            if ((c == 1 && isosrted(p[i])) || c == g) {
                ss.add(p[i]);
            }
        }
 
        // Lexicographically largest string
        for (let i of ss) {
            k += i;
        }
        return k;
    }
 
    // Driver code
 
    let S = "peek fit and run";
    let B = "ekta";
    let N = S.length;
    document.write(choosestr(S, B, N));
 
    // This code is contributed by rakeshsahni
 
</script>

peekfit

Complejidad temporal: O(N)
Espacio auxiliar: O(N)