Dados dos enteros N y K . La tarea es imprimir la string lexicográficamente más pequeña de longitud N que consta de alfabetos ingleses en minúsculas de modo que la suma de los caracteres de la string sea igual a K donde ‘a’ = 1, ‘b’ = 2, ‘c’ = 3 , ….. y ‘z’ = 26 .
Ejemplos:
Entrada: N = 5, K = 42
Salida: aaamz
“aaany”, “babmx”, “aablz”, etc. también son strings válidas
pero “aaamz” es lexicográficamente la más pequeña.
Entrada: N = 3, K = 25
Salida: aaw
Acercarse:
- Inicialice la array de caracteres de tamaño N y complete todo el elemento con ‘a’ .
- Comience a recorrer desde el final de la array y reemplace los elementos de la array por ‘z’ si K ≥ 26 o reemplácelo por el carácter que tiene valor ASCII (K + 97 – 1) .
- Al mismo tiempo, disminuya el valor de K por el valor del elemento reemplazado, es decir, para a = 1 , b = 2 , c = 3 , …, z = 26 .
- Además, tenga en cuenta que estamos restando el valor del elemento anterior, es decir, (total ‘a’) antes del elemento actual y sumando lo mismo antes del final del ciclo for.
- Compruebe la condición K < 0 y rompa el bucle for.
- Devuelve la nueva string formada por los elementos de la array char como respuesta.
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 return the lexicographically
// smallest string of length n that
// satisfies the given condition
string lexo_small(int n, int k)
{
string arr = "";
for(int i = 0; i < n; i++)
arr += 'a';
// Iteration from the last position
// in the array
for (int i = n - 1; i >= 0; i--)
{
k -= i;
// If k is a positive integer
if (k >= 0)
{
// 'z' needs to be inserted
if (k >= 26)
{
arr[i] = 'z';
k -= 26;
}
// Add the required character
else
{
char c= (char)(k + 97 - 1);
arr[i] = c;
k -= arr[i] - 'a' + 1;
}
}
else
break;
k += i;
}
return arr;
}
// Driver code
int main()
{
int n = 5, k = 42;
string arr = lexo_small(n, k);
cout << arr;
}
// This code is contributed by Mohit Kumar
Java
// Java implementation of the approach
import java.util.Arrays;
public class Main {
// Function to return the lexicographically
// smallest string of length n that
// satisfies the given condition
public static char[] lexo_small(int n, int k)
{
char arr[] = new char[n];
Arrays.fill(arr, 'a');
// Iteration from the last position
// in the array
for (int i = n - 1; i >= 0; i--) {
k -= i;
// If k is a positive integer
if (k >= 0) {
// 'z' needs to be inserted
if (k >= 26) {
arr[i] = 'z';
k -= 26;
}
// Add the required character
else {
arr[i] = (char)(k + 97 - 1);
k -= arr[i] - 'a' + 1;
}
}
else
break;
k += i;
}
return arr;
}
// Driver code
public static void main(String[] args)
{
int n = 5, k = 42;
char arr[] = lexo_small(n, k);
System.out.print(new String(arr));
}
}
Python3
# Python implementation of the approach
# Function to return the lexicographically
# smallest string of length n that
# satisfies the given condition
def lexo_small(n, k):
arr = "";
for i in range(n):
arr += 'a';
# Iteration from the last position
# in the array
for i in range(n-1,-1,-1):
k -= i;
# If k is a positive integer
if (k >= 0):
# 'z' needs to be inserted
if (k >= 26):
arr = arr[:i] + 'z' + arr[i+1:];
k -= 26;
# Add the required character
else:
c= (k + 97 - 1);
arr = arr[:i] + chr(c) + arr[i+1:];
k -= ord(arr[i]) - ord('a') + 1;
else:
break;
k += i;
return arr;
# Driver code
if __name__ == '__main__':
n = 5; k = 42;
arr = lexo_small(n, k);
print(arr);
# This code contributed by PrinciRaj1992
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the lexicographically
// smallest string of length n that
// satisfies the given condition
public static char[] lexo_small(int n, int k)
{
char []arr = new char[n];
int i;
for(i = 0; i < n; i++)
arr[i] = 'a' ;
// Iteration from the last position
// in the array
for (i = n - 1; i >= 0; i--)
{
k -= i;
// If k is a positive integer
if (k >= 0)
{
// 'z' needs to be inserted
if (k >= 26)
{
arr[i] = 'z';
k -= 26;
}
// Add the required character
else
{
arr[i] = (char)(k + 97 - 1);
k -= arr[i] - 'a' + 1;
}
}
else
break;
k += i;
}
return arr;
}
// Driver code
public static void Main()
{
int n = 5, k = 42;
char []arr = lexo_small(n, k);
Console.WriteLine(new string(arr));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// javascript implementation of the approach
// Function to return the lexicographically
// smallest string of length n that
// satisfies the given condition
function lexo_small(n , k)
{
var arr = Array.from({length: n}, (_, i) => 'a');
// Iteration from the last position
// in the array
for (var i = n - 1; i >= 0; i--) {
k -= i;
// If k is a positive integer
if (k >= 0) {
// 'z' needs to be inserted
if (k >= 26) {
arr[i] = 'z';
k -= 26;
}
// Add the required character
else {
arr[i] = String.fromCharCode(k + 97 - 1);
k -= arr[i] - 'a' + 1;
}
}
else
break;
k += i;
}
return arr;
}
// Driver code
var n = 5, k = 42;
var arr = lexo_small(n, k);
document.write(arr.join(''));
// This code contributed by shikhasingrajput
</script>
Producción:
aaamz
Publicación traducida automáticamente
Artículo escrito por Rohan_Kansara y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA