Compruebe si String se puede generar concatenando caracteres o String en sí mismo

Dada una string de destino S que consta de letras en minúsculas, la tarea es crear esta string realizando alguna operación en una string vacía tal que:

• La primera operación es agregar un alfabeto en minúsculas a la string S y 
• La segunda operación es agregar una copia de S a sí mismo. 

Nota: La primera operación no se puede utilizar continuamente dos veces.

Ejemplos:

Entrada: S = “xxyxxy”
Salida: Sí

Explicación: Primero agregue ‘x’ a la string vacía S. Ahora S = ”x” .
Utilice la segunda operación. La string será S = “xx” .
Agregue ‘y’ con la string. Entonces la string actual es «xxy» .
Por último, realice la operación 2 para obtener la string dada que es «xxyxxy» . 
Por lo tanto, es posible hacer que la string dada sea S después de realizar las operaciones.

Entrada: S = ”abeja”

Salida: No

Planteamiento: El problema se puede resolver con base en la siguiente observación: 

Observaciones:

• El primer tipo de operación se puede aplicar cuando la string está vacía o inmediatamente después de que se haya realizado una operación del segundo tipo en la string. 
• Después de cada operación del segundo tipo, la longitud de la string resultante es uniforme. Por lo tanto, la operación del primer tipo solo se puede aplicar cuando la longitud de la string es par y finalmente da como resultado una string de longitud impar.
• Esto significa que si la longitud de la string es par, la última operación realizada en ella debe ser del segundo tipo; de lo contrario, si la longitud de la string es impar, la última operación realizada en ella debe ser del primer tipo.

Siga los pasos mencionados a continuación para implementar la idea anterior:

• Comienza con la string dada y sigue moviéndote hasta que la string se vacíe:
• Si el tamaño de la string actual es impar,  
  • Eliminar el último carácter de la string (operación del primer tipo).
• Si el tamaño de la string actual es par,  
  • Compruebe si esta string es la copia de dos strings iguales (operación del segundo tipo) y reduzca el tamaño de la string a la mitad. 
  • Si la string actual no se puede obtener mediante una sola operación del segundo tipo, deje de iterar.
• Si la string está vacía al final, se puede construir con estas operaciones; de lo contrario, no se puede construir con estas operaciones.

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

// Java code to implement the approach
  
import java.io.*;
import java.util.*;
  
class GFG {
  
    // Function to check whether given string
    // is possible to make it from empty
    // string after performing operation
    public static void checkString(String A, int N)
    {
        while (N != 0) {
            int mid = N / 2;
            if (N % 2 == 0) {
                if (A.substring(0, mid).equals(
                        A.substring(mid))) {
                    A = A.substring(0, mid);
                    N = mid;
                }
                else {
                    break;
                }
            }
            else {
                if (A.substring(0, mid).equals(
                        A.substring(mid, N - 1))) {
                    A = A.substring(0, mid);
                    N = mid;
                }
                else {
                    break;
                }
            }
        }
        if (N == 0 || N == 1)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
  
    // Driver code
    public static void main(String[] args)
    {
        String S = "xxyxxy";
        int N = S.length();
  
        // Function call
        checkString(S, N);
    }
}

Yes

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