Compruebe si las substrings de tres strings dadas se pueden concatenar para formar un palíndromo

https://write.geeksforgeeks.org/internshipDadas tres strings S1 , S2 y S3 de longitudes L , M y N respectivamente, la tarea es verificar si es posible elegir algunas substrings no vacías de S1, S2 , y S3 tales que su concatenación es un palíndromo . Si es cierto, escriba «SÍ» . De lo contrario, escriba “NO”.

Ejemplos:

Entrada: S1 = “adcb”, S2 = “bcdb”, S3 = “ace”
Salida: SÍ
Explicación: 
Una de las formas posibles es la siguiente:
Seleccione la substring “ad” de la string S1, “d” de la string S2 , y “a” de la string S3. Por tanto, la string resultante es S = “adda”, que es un palíndromo. Por lo tanto, la salida debe ser «SÍ».

Entrada: S1 = “a”, S2 = “bc”, S3 = “c”
Salida: NO

Enfoque: La idea es observar que siempre es posible encontrar a , b y c tales que a+b+c se conviertan en palíndromos si S1 y S3 tienen al menos un carácter común. Siga los pasos a continuación para resolver el problema:

1. Inicialice dos variables, digamos maskA y maskC , para enmascarar los caracteres en las strings S1 y S3 respectivamente.
2. Iterar sobre los caracteres de la string S1 y establecer (i-‘a’) el bit en ^maskA , lo que indica que el carácter respectivo está presente en la string S1 .
3. Iterar sobre los caracteres de la string S3 y establecer (i-‘a’) el bit en ^maskC , lo que indica que el carácter respectivo está presente en la string S3 .
4. Si el AND bit a bit de maskA y maskC es mayor que cero, entonces imprima «SÍ» . De lo contrario, escriba “NO” .

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if substrings from
// three given strings can be concatenated
// to form a palindrome
string make_palindrome(
    string S1, string S2, string S3)
{
    // Mask for S1 and S2
    int maskA = 0, maskC = 0;
 
    // Set (i-'a')th bit in maskA
    for (char i : S1)
        maskA |= (1 << (i - 'a'));
 
    // Set (i-'a')th bit in maskC
    for (char i : S3)
        maskC |= (1 << (i - 'a'));
 
    // If the bitwise AND is > 0
    if ((maskA & maskC) > 0)
        return "YES";
 
    return "NO";
}
 
// Driver Code
int main()
{
    string S1 = "adcb", S2 = "bcdb", S3 = "abe";
    cout << make_palindrome(S1, S2, S3);
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to check if subStrings from
// three given Strings can be concatenated
// to form a palindrome
static String make_palindrome(
    String S1, String S2, String S3)
{
   
    // Mask for S1 and S2
    int maskA = 0, maskC = 0;
 
    // Set (i-'a')th bit in maskA
    for (char i : S1.toCharArray())
        maskA |= (1 << (i - 'a'));
 
    // Set (i-'a')th bit in maskC
    for (char i : S3.toCharArray())
        maskC |= (1 << (i - 'a'));
 
    // If the bitwise AND is > 0
    if ((maskA & maskC) > 0)
        return "YES";
    return "NO";
}
 
// Driver Code
public static void main(String[] args)
{
    String S1 = "adcb", S2 = "bcdb", S3 = "abe";
    System.out.print(make_palindrome(S1, S2, S3));
}
}
 
// This code is contributed by shikhasingrajput

# Python3 program for the above approach
 
# Function to check if substrings from
# three given strings can be concatenated
# to form a palindrome
def make_palindrome(S1, S2, S3):
   
    # Mask for S1 and S2
    maskA, maskC = 0, 0
 
    # Set (i-'a')th bit in maskA
    for i in S1:
        maskA |= (1 << (ord(i) - ord('a')))
 
    # Set (i-'a')th bit in maskC
    for i in S3:
        maskC |= (1 << (ord(i) - ord('a')))
 
    # If the bitwise AND is > 0
    if ((maskA & maskC) > 0):
        return "YES"
 
    return "NO"
 
# Driver Code
if __name__ == '__main__':
    S1,S2,S3 = "adcb", "bcdb", "abe"
    print (make_palindrome(S1, S2, S3))
 
    # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
public class GFG
{
 
// Function to check if subStrings from
// three given Strings can be concatenated
// to form a palindrome
static String make_palindrome(
    String S1, String S2, String S3)
{
   
    // Mask for S1 and S2
    int maskA = 0, maskC = 0;
 
    // Set (i-'a')th bit in maskA
    foreach (char i in S1.ToCharArray())
        maskA |= (1 << (i - 'a'));
 
    // Set (i-'a')th bit in maskC
    foreach (char i in S3.ToCharArray())
        maskC |= (1 << (i - 'a'));
 
    // If the bitwise AND is > 0
    if ((maskA & maskC) > 0)
        return "YES";
    return "NO";
}
 
// Driver Code
public static void Main(String[] args)
{
    String S1 = "adcb", S2 = "bcdb", S3 = "abe";
    Console.Write(make_palindrome(S1, S2, S3));
}
}
 
// This code is contributed by Rajput-Ji

<script>
// Javascript program for the above approach
 
// Function to check if subStrings from
// three given Strings can be concatenated
// to form a palindrome
function make_palindrome(S1,S2,S3)
{
    // Mask for S1 and S2
    let maskA = 0, maskC = 0;
  
    // Set (i-'a')th bit in maskA
    for (let i=0;i< S1.length;i++)
        maskA |= (1 << (S1[i].charCodeAt(0) - 'a'.charCodeAt(0)));
  
    // Set (i-'a')th bit in maskC
    for (let i=0;i< S3.length;i++)
        maskC |= (1 << (S3[i].charCodeAt(0) - 'a'.charCodeAt(0)));
  
    // If the bitwise AND is > 0
    if ((maskA & maskC) > 0)
        return "YES";
    return "NO";
}
 
// Driver Code
let S1 = "adcb", S2 = "bcdb", S3 = "abe";
document.write(make_palindrome(S1, S2, S3));
 
 
// This code is contributed by unknown2108
</script>

YES

Complejidad temporal: O(L + N)
Espacio auxiliar: O(L + M + N)