Dada una string S y un rango L y R, la tarea es imprimir la string lexicográficamente más grande que se puede formar a partir de los caracteres en el rango L y R.
Ejemplos :
Input: str = "thgyfh", L = 2, R = 6 Output: yhhgf Input: str = "striver", L = 3, R = 5 Output: vri
Enfoque :
- Iterar de min(L, R) a max(L, R) y aumentar las frecuencias de los caracteres en una array freq[].
- Iterar de 25 a 0 e imprimir el número de veces que aparece cada carácter para obtener la string lexicográficamente más grande.
El punto común de error que todos cometen es que iteran de L a R en lugar de min(L, R) a max(L, R) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print the
// lexicographically largest string that
// can be formed from the characters
// in range L and R
#include <bits/stdc++.h>
using namespace std;
// Function to return the lexicographically largest string
string printLargestString(string s, int l, int r)
{
// hash array
int freq[26] = { 0 };
// make 0-based indexing
l--;
r--;
// iterate and count frequencies of character
for (int i = min(l, r); i <= max(l, r); i++) {
freq[s[i] - 'a']++;
}
// ans string
string ans = "";
// iterate in frequency array
for (int i = 25; i >= 0; i--) {
// add till all characters
// are added
while (freq[i]) {
ans += char('a' + i);
freq[i]--;
}
}
return ans;
}
// Driver Code
int main()
{
string s = "striver";
int l = 3, r = 5;
cout << printLargestString(s, l, r);
return 0;
}
Java
// Java program to print the
// lexicographically largest String that
// can be formed from the characters
// in range L and R
class GFG {
// Function to return the lexicographically largest String
static String printLargestString(String s, int l, int r) {
// hash array
int freq[] = new int[26];
// make 0-based indexing
l--;
r--;
// iterate and count frequencies of character
for (int i = Math.min(l, r); i <= Math.max(l, r); i++) {
freq[s.charAt(i) - 'a']++;
}
// ans String
String ans = "";
// iterate in frequency array
for (int i = 25; i >= 0; i--) {
// add till all characters
// are added
while (freq[i] > 0) {
ans += (char) ('a' + i);
freq[i]--;
}
}
return ans;
}
// Driver Code
public static void main(String[] args) {
String s = "striver";
int l = 3, r = 5;
System.out.println(printLargestString(s, l, r));
}
}
/* This JAVA code is contributed by 29AjayKumar*/
Python 3
# Python 3 program to print the
# lexicographically largest string that
# can be formed from the characters
# in range L and R
# Function to return the lexicographically
# largest string
def printLargestString(s, l, r):
# hash array
freq = [0] * 26
# make 0-based indexing
l -= 1
r -= 1
# iterate and count frequencies of character
for i in range(min(l, r), max(l, r) + 1) :
freq[ord(s[i]) - ord('a')] += 1
# ans string
ans = ""
# iterate in frequency array
for i in range(25, -1, -1):
# add till all characters are added
while (freq[i]):
ans += chr(ord('a') + i)
freq[i] -= 1
return ans
# Driver Code
if __name__ == "__main__":
s = "striver"
l = 3
r = 5
print(printLargestString(s, l, r))
# This code is contributed by ita_c
C#
// C# program to print the lexicographically
// largest String that can be formed from the
// characters in range L and R
using System;
class GFG
{
// Function to return the lexicographically
// largest String
static String printLargestString(String s,
int l, int r)
{
// hash array
int []freq = new int[26];
// make 0-based indexing
l--;
r--;
// iterate and count frequencies
// of character
for (int i = Math.Min(l, r);
i <= Math.Max(l, r); i++)
{
freq[s[i] - 'a']++;
}
// ans String
String ans = "";
// iterate in frequency array
for (int i = 25; i >= 0; i--)
{
// add till all characters
// are added
while (freq[i] > 0)
{
ans += (char) ('a' + i);
freq[i]--;
}
}
return ans;
}
// Driver Code
public static void Main()
{
String s = "striver";
int l = 3, r = 5;
Console.Write(printLargestString(s, l, r));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to print the
// lexicographically largest String that
// can be formed from the characters
// in range L and R
// Function to return the lexicographically largest String
function printLargestString( s , l , r) {
// hash array
var freq = Array(26).fill(0);
// make 0-based indexing
l--;
r--;
// iterate and count frequencies of character
for (i = Math.min(l, r); i <= Math.max(l, r); i++) {
freq[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
}
// ans String
var ans = "";
// iterate in frequency array
for (var i = 25; i >= 0; i--) {
// add till all characters
// are added
while (freq[i] > 0) {
ans += String.fromCharCode('a'.charCodeAt(0) + i);
freq[i]--;
}
}
return ans;
}
// Driver Code
var s = "striver";
var l = 3, r = 5;
document.write(printLargestString(s, l, r));
// This code is contributed by todaysgaurav
</script>
Producción:
vri
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces para contar las frecuencias.
Cada elemento se agrega a la tabla de frecuencia solo una vez, lo que toma O (1) y se agrega a la string que también toma O (1).
Espacio auxiliar: O (N), ya que estamos usando espacio adicional para almacenar la string resultante.