Compruebe si se puede formar una string palindrómica concatenando substrings de dos strings dadas

Dadas dos strings str1 y str2 , la tarea es comprobar si es posible formar una String Palindrómica mediante la concatenación de dos substrings de str1 y str2 .

Ejemplos:

Entrada: str1 = “abcd”, str2 = “acba”
Salida: Sí
Explicación:
Hay cinco casos posibles en los que la concatenación de dos substrings de str1 y str2 da una string palindrómica:
“ab” + “a” = “aba”
“ab” + “ba” = “abba”
“bc” + “cb” = “bccb”
“bc” + “b” = “bcb”
“cd” + “c” = “cdc”

Entrada: str1 = «pqrs», str2 = «abcd»
Salida: No
Explicación:
No hay una concatenación posible de substrings de strings dadas que da una string palindrómica.

Enfoque ingenuo:
el enfoque más simple para resolver el problema es generar todas las substrings posibles de str1 y str2 y combinarlas para generar todas las concatenaciones posibles. Para cada concatenación, compruebe si es palindrómica o no. Si es cierto, escriba “Sí” . De lo contrario, escriba “No” .
Complejidad de tiempo: O(N ² * M ² * (N+M)), donde N y M son las longitudes de str1 y str2 respectivamente.
Espacio Auxiliar: O(1)

Enfoque eficiente:
Para optimizar el enfoque anterior, es necesario hacer la siguiente observación:

Si las strings dadas poseen al menos un carácter común, siempre formarán una string palindrómica al concatenar el carácter común de ambas strings. 
Ilustración:
str1 = “ a bc”, str2 = “f a d” 
Dado que ‘a’ es común en ambas strings, se puede obtener una string palindrómica “ aa ”. 

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

• Inicialice una array booleana para marcar la presencia de cada alfabeto en las dos strings.
• Recorra str1 y marque el índice (str1[i] – ‘a’) como verdadero.
• Ahora, recorra str2 y compruebe si algún índice (str2[i] – ‘a’) ya está marcado como verdadero , imprima «Sí» .
• Después de completar el recorrido de str2 , si no se encuentra ningún carácter común, imprima «No».

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 check if a palindromic
// string can be formed from the
// substring of given strings
bool check(string str1, string str2)
{
    // Boolean array to mark
    // presence of characters
    vector<bool> mark(26, false);
 
    int n = str1.size(),
        m = str2.size();
 
    for (int i = 0; i < n; i++) {
 
        mark[str1[i] - 'a'] = true;
    }
 
    // Check if any of the character
    // of str2 is already marked
    for (int i = 0; i < m; i++) {
 
        // If a common character
        // is found
        if (mark[str2[i] - 'a'])
            return true;
    }
 
    // If no common character
    // is found
    return false;
}
 
// Driver Code
int main()
{
 
    string str1 = "abca",
        str2 = "efad";
 
    if (check(str1, str2))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.Arrays;
 
class GFG{
     
// Function to check if a palindromic
// string can be formed from the
// substring of given strings
public static boolean check(String str1,
                            String str2)
{
     
    // Boolean array to mark
    // presence of characters
    boolean[] mark = new boolean[26];
    Arrays.fill(mark, false);
     
    int n = str1.length(),
        m = str2.length();
 
    for(int i = 0; i < n; i++)
    {
        mark[str1.charAt(i) - 'a'] = true;
    }
 
    // Check if any of the character
    // of str2 is already marked
    for(int i = 0; i < m; i++)
    {
 
        // If a common character
        // is found
        if (mark[str2.charAt(i) - 'a'])
            return true;
    }
 
    // If no common character
    // is found
    return false;
}
 
// Driver code
public static void main(String[] args)
{
    String str1 = "abca",
    str2 = "efad";
 
    if (check(str1, str2))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program to implement
# the above approach
     
# Function to check if a palindromic
# string can be formed from the
# substring of given strings
def check(str1, str2):
     
    # Boolean array to mark
    # presence of characters
    mark = [False for i in range(26)]
     
    n = len(str1)
    m = len(str2)
     
    for i in range(n):
        mark[ord(str1[i]) - ord('a')] = True
     
    # Check if any of the character
    # of str2 is already marked
    for i in range(m):
         
        # If a common character
        # is found
        if (mark[ord(str2[i]) - ord('a')]):
            return True;
 
    # If no common character
    # is found
    return False
     
# Driver code
if __name__=="__main__":
     
    str1 = "abca"
    str2 = "efad"
 
    if (check(str1, str2)):
        print("Yes");
    else:
        print("No");
 
# This code is contributed by rutvik_56

// C# program to implement
// the above approach
using System;
 
class GFG{
     
// Function to check if a palindromic
// string can be formed from the
// substring of given strings
public static bool check(String str1,
                        String str2)
{
     
    // Boolean array to mark
    // presence of characters
    bool[] mark = new bool[26];
     
    int n = str1.Length,
        m = str2.Length;
 
    for(int i = 0; i < n; i++)
    {
        mark[str1[i] - 'a'] = true;
    }
 
    // Check if any of the character
    // of str2 is already marked
    for(int i = 0; i < m; i++)
    {
 
        // If a common character
        // is found
        if (mark[str2[i] - 'a'])
            return true;
    }
 
    // If no common character
    // is found
    return false;
}
 
// Driver code
public static void Main(String[] args)
{
    String str1 = "abca",
    str2 = "efad";
 
    if (check(str1, str2))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// Javascript Program to implement
// the above approach
 
// Function to check if a palindromic
// string can be formed from the
// substring of given strings
function check(str1, str2)
{
    // Boolean array to mark
    // presence of characters
    var mark = Array(26).fill(false);
 
    var n = str1.length,
        m = str2.length;
 
    for (var i = 0; i < n; i++) {
 
        mark[str1[i] - 'a'] = true;
    }
 
    // Check if any of the character
    // of str2 is already marked
    for (var i = 0; i < m; i++) {
 
        // If a common character
        // is found
        if (mark[str2[i] - 'a'])
            return true;
    }
 
    // If no common character
    // is found
    return false;
}
 
// Driver Code
var str1 = "abca",
    str2 = "efad";
if (check(str1, str2))
    document.write( "Yes");
else
    document.write( "No");
 
// This code is contributed by noob2000.
</script>

Yes

Complejidad de tiempo: O(max(N, M)) donde N y M son las longitudes de str1 y str2 respectivamente.  Como, estamos atravesando ambas cuerdas.
Espacio auxiliar: O(1), ya que estamos usando cualquier espacio adicional.