String lexicográficamente más pequeña que usa todas las primeras K letras del alfabeto y no hay dos caracteres adyacentes iguales

Dados dos números enteros N y K , la tarea es formar una string de tamaño N usando los primeros K caracteres del alfabeto siguiendo las condiciones dadas:

• No hay dos caracteres adyacentes de la string que sean iguales.
• Todos los caracteres K están presentes al menos una vez en la string.

Si no es posible tal string, imprima -1.

Ejemplos:

Entrada: N = 3, K = 2
Salida: “aba”
Explicación: Esta es la string lexicográficamente más pequeña que sigue a la condición.
“aaa” es lexicográficamente la string más pequeña de tamaño 3, pero no contiene ‘b’.
Por lo tanto, no es una string válida de acuerdo con la declaración.
“aab” también es lexicográficamente más pequeño, pero viola la condición de que dos caracteres adyacentes no sean iguales.

Entrada: N = 2, K = 3
Salida: -1
Explicación: Debe elegir los primeros 3 caracteres, pero se debe formar una string de solo 2 tamaños.
Por lo tanto, no es posible utilizar todos los primeros 3 caracteres.

Enfoque: Este es un problema basado en la implementación. Como se sabe, si los caracteres iniciales del alfabeto se utilizan al principio de la string, la string será lexicográficamente más pequeña. Siga los pasos que se mencionan a continuación:

• si N < K o K = 1 y N > 1 , imprima ‘-1’ como formando una string que satisfaga ambas condiciones, no es posible.
• De lo contrario, si N = 2 , imprima «ab» .
• Si N > 2 , agregue ‘a’ y ‘b’ en la string resultante alternativamente hasta que la longitud restante sea K-2 . Luego agregue los caracteres restantes excepto ‘a’ y ‘b’ en orden lexicográfico.
• La string final es la string requerida.

A continuación se muestra la implementación del enfoque anterior.

// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the
// lexicographically smallest string
string findmin(int N, int K)
{
    // If size of given string is
    // more than first K letters of
    // alphabet then print -1.
    // If K = 1 and N > 1 then it
    // violates the rule that
    // adjacent characters should be different
    if (N < K or (K == 1 and N > 1))
        return "-1";
 
    // If N = 2 then print "ab"
    if (N == 2)
        return "ab";
 
    string s;
    // Except "ab" add characters
    // in the string
    for (int i = 2; i < K; i++) {
        s += char(i + 97);
    }
    string a = "ab", b;
    int i = 0;
    while (i < N) {
 
        // Add 'a' and 'b' alternatively
        b += a[i % 2];
        i++;
 
        // If there are other characters
        // than 'a' and 'b'
        if (N - i == K - 2) {
            for (int i = 0; i < s.size();
                 i++) {
                b += s[i];
            }
            break;
        }
    }
 
    // Desired string
    return b;
}
 
// Driver code
int main()
{
    int N = 3, K = 2;
 
    // Function call
    cout << findmin(N, K);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to find the
  // lexicographically smallest string
  static String findmin(int N, int K)
  {
     
    // If size of given string is
    // more than first K letters of
    // alphabet then print -1.
    // If K = 1 and N > 1 then it
    // violates the rule that
    // adjacent characters should be different
    if (N < K || (K == 1 && N > 1))
      return "-1";
 
    // If N = 2 then print "ab"
    if (N == 2)
      return "ab";
 
    String s = "";
    // Except "ab" add characters
    // in the string
    for (int i = 2; i < K; i++) {
      char ch = (char)(i + 97);
      s += ch;
    }
    String a = "ab", b = "";
    int i = 0;
    while (i < N) {
 
      // Add 'a' and 'b' alternatively
      b += a.charAt(i % 2);
      i++;
 
      // If there are other characters
      // than 'a' and 'b'
      if (N - i == K - 2) {
        for (int j = 0; j < s.length();j++) {
          b += s.charAt(j);
        }
        break;
      }
    }
 
    // Desired string
    return b;
  }
 
  // Driver code
  public static void main (String[] args) {
 
    int N = 3, K = 2;
    System.out.println(findmin(N, K));
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python program to implement the approach
 
# Function to find the
# lexicographically smallest string
def findmin(N, K):
 
    # If size of given string is
    # more than first K letters of
    # alphabet then print -1.
    # If K = 1 and N > 1 then it
    # violates the rule that
    # adjacent characters should be different
    if (N < K or (K == 1 and N > 1)):
        return "-1"
 
    # If N = 2 then print "ab"
    if (N == 2):
        return "ab"
 
    s = ""
    # Except "ab" add characters
    # in the string
    for i in range(2, K):
        s += (i + 97)
 
    a = "ab"
    b = ""
    i = 0
    while (i < N):
 
        # Add 'a' and 'b' alternatively
        b += a[i % 2]
        i += 1
 
        # If there are other characters
        # than 'a' and 'b'
        if (N - i == K - 2):
            for j in range(len(s)):
                b += s[i]
            break
 
    # Desired string
    return b
 
# Driver code
N = 3
K = 2
 
# Function call
print(findmin(N, K))
 
# This code is contributed by Samim Hossain Mondal.

// C# program to implement the approach
using System;
class GFG
{
 
  // Function to find the
  // lexicographically smallest string
  static string findmin(int N, int K)
  {
 
    // If size of given string is
    // more than first K letters of
    // alphabet then print -1.
    // If K = 1 and N > 1 then it
    // violates the rule that
    // adjacent characters should be different
    if (N < K || (K == 1 && N > 1))
      return "-1";
 
    // If N = 2 then print "ab"
    if (N == 2)
      return "ab";
 
    string s = "";
 
    // Except "ab" add characters
    // in the string
    for (int x = 2; x < K; x++) {
      s += (char)(x + 97);
    }
    string a = "ab", b = "";
    int i = 0;
    while (i < N) {
 
      // Add 'a' and 'b' alternatively
      b += a[i % 2];
      i++;
 
      // If there are other characters
      // than 'a' and 'b'
      if (N - i == K - 2) {
        for (int j = 0; j < s.Length;
             j++) {
          b += s[j];
        }
        break;
      }
    }
 
    // Desired string
    return b;
  }
 
  // Driver code
  public static void Main()
  {
    int N = 3, K = 2;
 
    // Function call
    Console.Write(findmin(N, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript program to implement the approach
 
    // Function to find the
    // lexicographically smallest string
    const findmin = (N, K) => {
     
        // If size of given string is
        // more than first K letters of
        // alphabet then print -1.
        // If K = 1 and N > 1 then it
        // violates the rule that
        // adjacent characters should be different
        if (N < K || (K == 1 && N > 1))
            return "-1";
 
        // If N = 2 then print "ab"
        if (N == 2)
            return "ab";
 
        let s = "";
        // Except "ab" add characters
        // in the string
        for (let i = 2; i < K; i++) {
            s += String.fromCharCode(i + 97);
        }
        let a = "ab", b = "";
        let i = 0;
        while (i < N) {
 
            // Add 'a' and 'b' alternatively
            b += a[i % 2];
            i++;
 
            // If there are other characters
            // than 'a' and 'b'
            if (N - i == K - 2) {
                for (let i = 0; i < s.length; i++) {
                    b += s[i];
                }
                break;
            }
        }
 
        // Desired string
        return b;
    }
 
    // Driver code
    let N = 3, K = 2;
 
    // Function call
    document.write(findmin(N, K));
 
    // This code is contributed by rakeshsahni
 
</script>

aba

Complejidad temporal: O(N)
Espacio auxiliar: O(N)