Dado un entero positivo K , la tarea es encontrar lexicográficamente la string más pequeña que se puede generar utilizando los primeros K alfabetos en minúsculas de modo que ninguna substring de longitud de al menos 2 se repita en la string generada.
Ejemplos:
Entrada: K = 3
Salida: aabacbbcca
Explicación:
En la string “aabacbbcca”, todas las substrings posibles de longitud de al menos 2 se repiten más de una vez.Entrada: K = 4
Salida: aabacadbbcbdccdda
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Si todas las substrings de longitud 2 son únicas, todas las substrings de longitud superior a 2 también serán únicas.
- Por lo tanto, la string de longitud máxima debe contener todas las substrings únicas de longitud 2 dispuestas en orden lexicográfico de modo que no haya 3 caracteres consecutivos iguales en la string.
Siga los pasos a continuación para resolver el problema:
- Inicialice una string , digamos S como la string vacía que almacena la string resultante.
- Itere sobre todos los primeros K caracteres del alfabeto en minúsculas usando la variable, diga i y realice los siguientes pasos:
- Agregue el carácter actual i a la string S .
- Iterar desde el (i + 1) th carácter hasta el K th carácter y agregar el carácter i seguido del carácter j a la string S .
- Agregue el carácter ‘a’ a la string S para que la substring que consta del último y el primer alfabeto también esté presente en la string resultante.
- Después de completar los pasos anteriores, imprima la string S como la string resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the lexicographically
// smallest string of the first K lower
// case alphabets having unique substrings
void generateString(int K)
{
// Stores the resultant string
string s = "";
// Iterate through all the characters
for (int i = 97; i < 97 + K; i++) {
s = s + char(i);
// Inner Loop for making pairs
// and adding them into string
for (int j = i + 1;
j < 97 + K; j++) {
s += char(i);
s += char(j);
}
}
// Adding first character so that
// substring consisting of the last
// the first alphabet is present
s += char(97);
// Print the resultant string
cout << s;
}
// Driver Code
int main()
{
int K = 4;
generateString(K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the lexicographically
// smallest string of the first K lower
// case alphabets having unique substrings
static void generateString(int K)
{
// Stores the resultant string
String s = "";
// Iterate through all the characters
for(int i = 97; i < 97 + K; i++)
{
s = s + (char)(i);
// Inner Loop for making pairs
// and adding them into string
for(int j = i + 1; j < 97 + K; j++)
{
s += (char)(i);
s += (char)(j);
}
}
// Adding first character so that
// substring consisting of the last
// the first alphabet is present
s += (char)(97);
// Print the resultant string
System.out.println(s);
}
// Driver code
public static void main(String []args)
{
int K = 4;
generateString(K);
}
}
// This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the lexicographically
// smallest string of the first K lower
// case alphabets having unique substrings
static void generateString(int K)
{
// Stores the resultant string
string s = "";
// Iterate through all the characters
for(int i = 97; i < 97 + K; i++)
{
s = s + (char)(i);
// Inner Loop for making pairs
// and adding them into string
for(int j = i + 1; j < 97 + K; j++)
{
s += (char)(i);
s += (char)(j);
}
}
// Adding first character so that
// substring consisting of the last
// the first alphabet is present
s += (char)(97);
// Print the resultant string
Console.Write(s);
}
// Driver Code
public static void Main()
{
int K = 4;
generateString(K);
}
}
// This code is contributed by ukasp
Python3
# python 3 program for the above approach # Function to find the lexicographically # smallest string of the first K lower # case alphabets having unique substrings def generateString(K): # Stores the resultant string s = "" # Iterate through all the characters for i in range(97,97 + K,1): s = s + chr(i); # Inner Loop for making pairs # and adding them into string for j in range(i + 1,97 + K,1): s += chr(i) s += chr(j) # Adding first character so that # substring consisting of the last # the first alphabet is present s += chr(97) # Print the resultant string print(s) # Driver Code if __name__ == '__main__': K = 4 generateString(K) # This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the lexicographically
// smallest string of the first K lower
// case alphabets having unique substrings
function generateString(K)
{
// Stores the resultant string
var s = "";
// Iterate through all the characters
for(var i = 97; i < 97 + K; i++)
{
s = s + String.fromCharCode(i);
// Inner Loop for making pairs
// and adding them into string
for(var j = i + 1; j < 97 + K; j++)
{
s += String.fromCharCode(i);
s += String.fromCharCode(j);
}
}
// Adding first character so that
// substring consisting of the last
// the first alphabet is present
s += String.fromCharCode(97);
// Print the resultant string
document.write(s);
}
// Driver code
var K = 4;
generateString(K);
// This code is contributed by 29AjayKumar
</script>
Producción:
aabacadbbcbdccdda
Complejidad de Tiempo: O(K 2 )
Espacio Auxiliar: O(K 2 )
Publicación traducida automáticamente
Artículo escrito por tejasdhanait y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA