Dada una string, encuentre la concatenación de todas las substrings en orden lexicográfico.
Ejemplos:
Entrada: s = “abc”
Salida: aababcbbcc
Las substrings de s en orden lexicográfico son “a”, “b”, “c”, “ab”, “abc”, “bc”. La concatenación de substrings es “a”+”ab”+”abc”+”b”+”bc”+”c” = “aababcbbcc”.
Entrada: s = “cba”
Salida: abbaccbcba
1. Encuentre todas las substrings de string y guárdelas en una array de strings. El tamaño de la array sería n*(n+1)/2 donde n es la longitud de la string de entrada.
2. Ordene la array de strings para que estén todas en orden lexicográfico.
3. Concatene las strings de la array de strings en otra string vacía.
C++
// CPP Program to create concatenation of all
// substrings in lexicographic order.
#include <bits/stdc++.h>
using
namespace
std;
string lexicographicSubConcat(string s)
{
int
n = s.length();
// Creating an array to store substrings
int
sub_count = n*(n+1)/2;
string arr[sub_count];
// finding all substrings of string
int
index = 0;
for
(
int
i = 0; i < n; i++)
for
(
int
len = 1; len <= n - i; len++)
arr[index++] = s.substr(i, len);
// Sort all substrings in lexicographic
// order
sort(arr, arr + sub_count);
// Concatenating all substrings
string res =
""
;
for
(
int
i = 0; i < sub_count; i++)
res += arr[i];
return
res;
}
int
main()
{
string s =
"abc"
;
cout << lexicographicSubConcat(s);
return
0;
}
Java
// Java Program to create concatenation of all
// substrings in lexicographic order.
import
java.util.*;
class
GFG
{
static
String lexicographicSubConcat(String s)
{
int
n = s.length();
// Creating an array to store substrings
int
sub_count = n*(n+
1
)/
2
;
String []arr =
new
String[sub_count];
// finding all substrings of string
int
index =
0
;
for
(
int
i =
0
; i < n; i++)
for
(
int
len =
1
; len <= n - i; len++)
{
arr[index++] = s.substring(i, i+len);
}
// Sort all substrings in lexicographic
// order
Arrays.sort(arr);
// Concatenating all substrings
String res =
""
;
for
(
int
i =
0
; i < sub_count; i++)
res += arr[i];
return
res;
}
// Driver code
public
static
void
main(String[] args)
{
String s =
"abc"
;
System.out.println(lexicographicSubConcat(s));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python Program to create concatenation of all
# substrings in lexicographic order.
def
lexicographicSubConcat(s):
n
=
len
(s);
# Creating an array to store substrings
sub_count
=
(n
*
(n
+
1
))
/
/
2
;
arr
=
[
0
]
*
sub_count;
# finding all substrings of string
index
=
0
;
for
i
in
range
(n):
for
j
in
range
(
1
,n
-
i
+
1
):
arr[index]
=
s[i:i
+
j];
index
+
=
1
;
# Sort all substrings in lexicographic
# order
arr.sort();
# Concatenating all substrings
res
=
"";
for
i
in
range
(sub_count):
res
+
=
arr[i];
return
res;
s
=
"abc"
;
(lexicographicSubConcat(s));
# This code is contributed by Princi Singh
C#
// C# Program to create concatenation of all
// substrings in lexicographic order.
using
System;
class
GFG
{
static
String lexicographicSubConcat(String s)
{
int
n = s.Length;
// Creating an array to store substrings
int
sub_count = n*(n+1)/2;
String []arr =
new
String[sub_count];
// finding all substrings of string
int
index = 0;
for
(
int
i = 0; i < n; i++)
for
(
int
len = 1; len <= n - i; len++)
{
arr[index++] = s.Substring(i, len);
}
// Sort all substrings in lexicographic
// order
Array.Sort(arr);
// Concatenating all substrings
String res =
""
;
for
(
int
i = 0; i < sub_count; i++)
res += arr[i];
return
res;
}
// Driver code
public
static
void
Main(String[] args)
{
String s =
"abc"
;
Console.WriteLine(lexicographicSubConcat(s));
}
}
/* This code contributed by PrinciRaj1992 */
JavaScript
<script>
// Javascript Program to create concatenation of all
// substrings in lexicographic order.
function
lexicographicSubConcat(s)
{
var
n = s.length;
// Creating an array to store substrings
var
sub_count = n*parseInt((n+1)/2);
var
arr = Array(sub_count);
// finding all substrings of string
var
index = 0;
for
(
var
i = 0; i < n; i++)
for
(
var
len = 1; len <= n - i; len++)
arr[index++] = s.substring(i,i+ len);
// Sort all substrings in lexicographic
// order
arr.sort();
// Concatenating all substrings
var
res =
""
;
for
(
var
i = 0; i < sub_count; i++)
res += arr[i];
return
res;
}
var
s =
"abc"
;
document.write( lexicographicSubConcat(s));
</script>
Producción:
aababcbbccComplejidad temporal: O(n 3 )
Espacio Auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por Shashank_Pathak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA