Genere una string de longitud N que tenga la substring palindrómica más larga de longitud K

Dados dos enteros N y K ( K ≤ N ), la tarea es obtener una string de longitud N tal que la longitud máxima de una substring palindrómica de esta string sea K .

Ejemplos:

Entrada: N = 5, K = 3 
Salida: “abacd” 
Explicación: Las substrings palindrómicas son “a”, “b”, “c”, “d” y “aba”. Por lo tanto, la substring palindrómica más larga de la string dada tiene una longitud de 3.

Entrada: N = 8, K = 4 
Salida: “abbacdef” 
Explicación: Las substrings palindrómicas son “a”, “b”, “c”, “d”, “e”, “f”, “bb”, “abba” . Por lo tanto, la substring palindrómica más larga de la string dada tiene una longitud de 4.

Enfoque: La idea se basa en la siguiente observación de que la string de cualquier longitud compuesta por un solo carácter siempre es palindrómica, por ejemplo, {‘a’, ‘bbbbb’, ‘ccc’}. Entonces, para generar una string con las condiciones requeridas, imprima ‘a’ K veces de manera que tenga una substring palindrómica más larga de longitud K y llene las ranuras N – K restantes con una secuencia no palindrómica.

Siga los pasos a continuación para resolver el problema:

• Imprime ‘a’ exactamente K veces.
• Considere una secuencia no palindrómica, digamos «bcd».
• Imprime la string.

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

// C++ program to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate a string of
// length N having longest palindromic
// substring of length K
void string_palindrome(int N, int K)
{
 
    // Fill first K characters with 'a'
    for (int i = 0; i < K; i++)
        cout << "a";
 
    // Stores a non-palindromic sequence
    // to be repeated for N - k slots
    string s = "bcd";
 
    // Print N - k remaining characters
    for (int i = 0; i < N - K; i++)
        cout << s[i % 3];
}
 
// Driver Code
int main()
{
 
    // Given N and K
    int N = 5, K = 3;
    string_palindrome(N, K);
 
    return 0;
}

// Java program to implement the above approach
import java.util.*;
 
class GFG
{
 
// Function to generate a String of
// length N having longest palindromic
// subString of length K
static void String_palindrome(int N, int K)
{
 
    // Fill first K characters with 'a'
    for (int i = 0; i < K; i++)
        System.out.print("a");
 
    // Stores a non-palindromic sequence
    // to be repeated for N - k slots
    String s = "bcd";
 
    // Print N - k remaining characters
    for (int i = 0; i < N - K; i++)
        System.out.print(s.charAt(i % 3));
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Given N and K
    int N = 5, K = 3;
    String_palindrome(N, K);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to implement the above approach
 
# Function to generate a string of
# length N having longest palindromic
# substring of length K
def string_palindrome(N, K):
 
    # Fill first K characters with 'a'
    for i in range(K):
        print("a", end = "")
 
    # Stores a non-palindromic sequence
    # to be repeated for N - k slots
    s = "bcd"
 
    # Print N - k remaining characters
    for i in range(N - K):
        print(s[i % 3], end = "")
 
# Driver Code
if __name__ == '__main__':
   
    # Given N and K
    N, K = 5, 3
    string_palindrome(N, K)
 
    # This code is contributed by mohit kumar 29

// C# program to implement the above approach
using System;
class GFG
{
     
    // Function to generate a String of
    // length N having longest palindromic
    // subString of length K
    static void String_palindrome(int N, int K)
    {
     
        // Fill first K characters with 'a'
        for (int i = 0; i < K; i++)
            Console.Write("a");
     
        // Stores a non-palindromic sequence
        // to be repeated for N - k slots
        string s = "bcd";
     
        // Print N - k remaining characters
        for (int i = 0; i < N - K; i++)
            Console.Write(s[i % 3]);
    }
     
    // Driver Code
    public static void Main(string[] args)
    {
     
        // Given N and K
        int N = 5, K = 3;
        String_palindrome(N, K);
    }
}
 
// This code is contributed by AnkThon

<script>
 
// JavaScript program for above approach
 
    // Function to generate a String of
    // length N having longest palindromic
    // subString of length K
    function String_palindrome(N, K)
    {
      
        // Fill first K characters with 'a'
        for (let i = 0; i < K; i++)
            document.write("a");
      
        // Stores a non-palindromic sequence
        // to be repeated for N - k slots
        let s = "bcd";
      
        // Print N - k remaining characters
        for (let i = 0; i < N - K; i++)
            document.write(s[i % 3]);
    }
 
 
// Driver Code
 
     // Given N and K
        let N = 5, K = 3;
        String_palindrome(N, K);
         
</script>

aaabc

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