Dada una string str y consultas Q. Cada consulta consta de un número X , la tarea es imprimir la X substring lexicográficamente más pequeña de la string dada str .
Ejemplos:
Entrada: str = “geek”, q[] = {1, 5, 10}
Salida:
e
ek
k
“e”, “e”, “ee”, “eek”, “ek”, “g”, “ge ”, “gee”, “geek” y “k” son
todas las substrings posibles ordenadas lexicográficamente.Entrada: str = “abcgdhge”, q[] = {15, 32}
Salida:
bcgdhge
gdhge
Enfoque: genere todas las substrings y guárdelas en cualquier estructura de datos y ordene esa estructura de datos lexicográficamente. En la solución a continuación, hemos utilizado un vector para almacenar todas las substrings y la función de clasificación incorporada las clasifica en el orden dado. Ahora, para cada consulta, imprima vec[X – 1] , que será la substring X más pequeña.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to pre-process the sub-strings
// in sorted order
void pre_process(vector<string>& substrings, string s)
{
int n = s.size();
// Generate all substrings
for (int i = 0; i < n; i++) {
string dup = "";
// Iterate to find all sub-strings
for (int j = i; j < n; j++) {
dup += s[j];
// Store the sub-string in the vector
substrings.push_back(dup);
}
}
// Sort the substrings lexicographically
sort(substrings.begin(), substrings.end());
}
// Driver code
int main()
{
string s = "geek";
// To store all the sub-strings
vector<string> substrings;
pre_process(substrings, s);
int queries[] = { 1, 5, 10 };
int q = sizeof(queries) / sizeof(queries[0]);
// Perform queries
for (int i = 0; i < q; i++)
cout << substrings[queries[i] - 1] << endl;
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to pre-process the sub-strings
// in sorted order
static void pre_process(String substrings[],String s)
{
int n = s.length();
// Generate all substrings
int count = 0;
for (int i = 0; i < n; i++)
{
String dup = "";
// Iterate to find all sub-strings
for (int j = i; j < n; j++)
{
dup += s.charAt(j);
// Store the sub-string in the vector
substrings[count++] = dup;
}
}
// Sort the substrings lexicographically
int size = substrings.length;
for(int i = 0; i < size-1; i++) {
for (int j = i + 1; j < substrings.length; j++)
{
if(substrings[i].compareTo(substrings[j]) > 0)
{
String temp = substrings[i];
substrings[i] = substrings[j];
substrings[j] = temp;
}
}
//sort(substrings.begin(), substrings.end());
}
}
// Driver code
public static void main(String args[])
{
String s = "geek";
// To store all the sub-strings
String substrings[] = new String[10];
pre_process(substrings, s);
int queries[] = { 1, 5, 10 };
int q = queries.length;
// Perform queries
for (int i = 0; i < q; i++)
System.out.println(substrings[queries[i]-1]);
}
}
// This code is contributed by
// Surendra_Gangwar
Python3
# Python3 implementation of the approach # Function to pre-process the sub-strings # in sorted order def pre_process(substrings, s) : n = len(s); # Generate all substrings for i in range(n) : dup = ""; # Iterate to find all sub-strings for j in range(i,n) : dup += s[j]; # Store the sub-string in the vector substrings.append(dup); # Sort the substrings lexicographically substrings.sort(); return substrings; # Driver code if __name__ == "__main__" : s = "geek"; # To store all the sub-strings substrings = []; substrings = pre_process(substrings, s); queries = [ 1, 5, 10 ]; q = len(queries); # Perform queries for i in range(q) : print(substrings[queries[i] - 1]); # This code is contributed by AnkitRai01
C#
// C# code for above given approach
using System;
class GFG
{
// Function to pre-process the sub-strings
// in sorted order
static void pre_process(String []substrings,String s)
{
int n = s.Length;
// Generate all substrings
int count = 0;
for (int i = 0; i < n; i++)
{
String dup = "";
// Iterate to find all sub-strings
for (int j = i; j < n; j++)
{
dup += s[j];
// Store the sub-string in the vector
substrings[count++] = dup;
}
}
// Sort the substrings lexicographically
int size = substrings.Length;
for(int i = 0; i < size-1; i++)
{
for (int j = i + 1; j < substrings.Length; j++)
{
if(substrings[i].CompareTo(substrings[j]) > 0)
{
String temp = substrings[i];
substrings[i] = substrings[j];
substrings[j] = temp;
}
}
//sort(substrings.begin(), substrings.end());
}
}
// Driver code
public static void Main(String []args)
{
String s = "geek";
// To store all the sub-strings
String []substrings = new String[10];
pre_process(substrings, s);
int []queries = { 1, 5, 10 };
int q = queries.Length;
// Perform queries
for (int i = 0; i < q; i++)
Console.WriteLine(substrings[queries[i]-1]);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript implementation of the approach
// Function to pre-process the sub-strings
// in sorted order
function pre_process(substrings, s)
{
var n = s.length;
// Generate all substrings
for (var i = 0; i < n; i++) {
var dup = "";
// Iterate to find all sub-strings
for (var j = i; j < n; j++) {
dup += s[j];
// Store the sub-string in the vector
substrings.push(dup);
}
}
// Sort the substrings lexicographically
substrings.sort();
}
// Driver code
var s = "geek";
// To store all the sub-strings
var substrings = [];
pre_process(substrings, s);
var queries = [1, 5, 10];
var q = queries.length;
// Perform queries
for (var i = 0; i < q; i++)
document.write( substrings[queries[i] - 1] + "<br>");
</script>
Producción:
e ek k
Complejidad de tiempo: O(N 2 *logN), ya que estamos usando una función de ordenación incorporada para ordenar una array de tamaño N*N. Donde N es la longitud de la string.
Espacio auxiliar: O(N 2 ), ya que estamos usando espacio adicional para almacenar las substrings.