Genere una string de tener N * N substrings no palindrómicas distintas

Dado un entero par N , la tarea es construir una string tal que el número total de substrings distintas de esa string que no son un palíndromo sea igual a N ² .

Ejemplos:  

Entrada: N = 2 
Salida: aabb 
Explicación: 
Todas las distintas substrings no palindrómicas son ab, abb, aab y aabb . 
Por lo tanto, el recuento de substrings no palindrómicas es 4 = 2 ²  
Entrada: N = 4 
Salida: cccczzzz 
Explicación: 
todas las substrings distintas no palindrómicas de la string son cz, czz, czzz, czzzz, ccz, cczz, cczzz, cczzzz, cccz, ccczz, ccczzz, ccczzzz, ccccz, cccczz, cccczzz, cccczzzz . 
El recuento de substrings no palindrómicas es 16. 

Enfoque:
Se puede observar que, si los primeros N caracteres de una string son iguales, seguidos de N caracteres idénticos diferentes de los primeros N caracteres, entonces el recuento de substrings no palindrómicas distintas será N ² .  

Prueba:

N = 3 
str = “aaabbb” 
La string se puede dividir en dos substrings de N caracteres cada una: “aaa” y “bbb” 
El primer carácter ‘a’ de la primera substring forma N substrings distintas no palindrómicas “ab”, “ abb”, “abbb” con la segunda substring. 
De manera similar, los dos primeros caracteres «aa» forman N substrings distintas no palindrómicas «aab», «aabb», «aabbb». 
De manera similar, los N – 2 caracteres restantes de la primera substring también forman N substrings distintas no palindrómicas. 
Por lo tanto, el número total de substrings no palindrómicas distintas es igual a N ² . 

Por lo tanto, para resolver el problema, imprima ‘a’ como los primeros N caracteres de la string y ‘b’ como los siguientes N caracteres de 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 construct a string
// having N*N non-palindromic substrings
void createString(int N)
{
    for (int i = 0; i < N; i++) {
        cout << 'a';
    }
    for (int i = 0; i < N; i++) {
        cout << 'b';
    }
}
 
// Driver Code
int main()
{
    int N = 4;
 
    createString(N);
    return 0;
}

// Java Program to implement
// the above approach
class GFG{
 
// Function to construct a string
// having N*N non-palindromic substrings
static void createString(int N)
{
    for (int i = 0; i < N; i++)
    {
        System.out.print('a');
    }
    for (int i = 0; i < N; i++)
    {
        System.out.print('b');
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 4;
 
    createString(N);
}
}
 
// This code is contributed by shivanisinghss2110

# Python3 program to implement
# the above approach
 
# Function to construct a string
# having N*N non-palindromic substrings
def createString(N):
 
    for i in range(N):
        print('a', end = '')
    for i in range(N):
        print('b', end = '')
 
# Driver Code
N = 4
 
createString(N)
 
# This code is contributed by Shivam Singh

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to construct a string
// having N*N non-palindromic substrings
static void createString(int N)
{
    for(int i = 0; i < N; i++)
    {
        Console.Write('a');
    }
    for(int i = 0; i < N; i++)
    {
        Console.Write('b');
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 4;
 
    createString(N);
}
}
 
// This code is contributed by Princi Singh

<script>
// JavaScript program for the above approach
 
// Function to construct a string
// having N*N non-palindromic substrings
function createString(N)
{
    for (let i = 0; i < N; i++)
    {
        document.write('a');
    }
    for (let i = 0; i < N; i++)
    {
        document.write('b');
    }
}
     
// Driver Code
 
        let N = 4;
   
    createString(N);
         
</script>

aaaabbbb

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