Dadas dos strings, compruebe qué string hace un palíndromo primero

Dadas dos strings ‘A’ y ‘B’ de igual longitud. Dos jugadores juegan un juego en el que ambos eligen un personaje de sus respectivas strings (primero elige de A y segundo de B) y lo coloca en una tercera string (que inicialmente está vacía). El jugador que logra hacer el palíndromo de la tercera cuerda, es el ganador. Si el primer jugador hace palíndromo primero, imprima ‘A’, de lo contrario, ‘B’. Si las strings se vacían y nadie puede hacer un palíndromo, imprima ‘B’. 

Ejemplos: 

Input : A = ab
        B = ab
Output : B
First player puts 'a' (from string A)
Second player puts 'a' (from string B) 
which make palindrome. 
The result would be same even if A picks
'b' as first character.

Input : A = aba
        B = cde
Output : A

Input : A = ab
        B = cd
Output : B
None of the string will be able to
make a palindrome (of length > 1)
in any situation. So B will win.

Después de tomar algunos ejemplos, podemos observar que ‘A’ (o primer jugador) solo puede ganar cuando tiene un personaje que aparece más de una vez y no está presente en ‘B’. 

Implementación:

// Given two strings, check which string
// makes palindrome first.
#include<bits/stdc++.h>
using namespace std;
 
const int MAX_CHAR = 26;
 
// returns winner of two strings
char stringPalindrome(string A, string B)
{
    // Count frequencies of characters in
    // both given strings
    int countA[MAX_CHAR] = {0};
    int countB[MAX_CHAR] = {0};
    int l1 = A.length(), l2 = B.length();
    for(int i=0; i<l1;i++)
        countA[A[i]-'a']++;
    for(int i=0; i<l2;i++)
        countB[B[i]-'a']++;
 
    // Check if there is a character that
    // appears more than once in A and does
    // not appear in B
    for (int i=0 ;i <26;i++)
        if ((countA[i] >1 && countB[i] == 0))
           return 'A';
 
    return 'B';
}
 
// Driver Code
int main()
{
    string a = "abcdea";
    string b = "bcdesg";
    cout << stringPalindrome(a,b);
    return 0;
}

// Java program to check which string
// makes palindrome first.
public class First_Palin {
 
    static final int MAX_CHAR = 26;
 
    // returns winner of two strings
    static char stringPalindrome(String A, String B)
    {
        // Count frequencies of characters in
        // both given strings
        int[] countA = new int[MAX_CHAR];
        int[] countB = new int[MAX_CHAR];
 
        int l1 = A.length();
        int l2 = B.length();
         
        for (int i = 0; i < l1; i++)
            countA[A.charAt(i) - 'a']++;
         
        for (int i = 0; i < l2; i++)
            countB[B.charAt(i) - 'a']++;
 
        // Check if there is a character that
        // appears more than once in A and does
        // not appear in B
        for (int i = 0; i < 26; i++)
            if ((countA[i] > 1 && countB[i] == 0))
                return 'A';
 
        return 'B';
    }
 
    // Driver Code
public static void main(String args[])
    {
        String a = "abcdea";
        String b = "bcdesg";
        System.out.println(stringPalindrome(a, b));
    }
}
// This code is contributed by Sumit Ghosh

# Given two strings, check which string
# makes palindrome first.
 
MAX_CHAR = 26
 
# returns winner of two strings
def stringPalindrome(A, B):
     
    # Count frequencies of characters
    # in both given strings
    countA = [0] * MAX_CHAR
    countB = [0] * MAX_CHAR
    l1 = len(A)
    l2 = len(B)
    for i in range(l1):
        countA[ord(A[i]) - ord('a')] += 1
    for i in range(l2):
        countB[ord(B[i]) - ord('a')] += 1
 
    # Check if there is a character that
    # appears more than once in A and
    # does not appear in B
    for i in range(26):
        if ((countA[i] > 1 and countB[i] == 0)):
            return 'A'
    return 'B'
 
# Driver Code
if __name__ == '__main__':
    a = "abcdea"
    b = "bcdesg"
    print(stringPalindrome(a, b))
 
# This code is contributed by Rajput-Ji

// C# program to check which string
// makes palindrome first.
using System;
 
class First_Palin {
 
    static int MAX_CHAR = 26;
 
    // returns winner of two strings
    static char stringPalindrome(string A, string B)
    {
        // Count frequencies of characters in
        // both given strings
        int[] countA = new int[MAX_CHAR];
        int[] countB = new int[MAX_CHAR];
 
        int l1 = A.Length;
        int l2 = B.Length;
         
        for (int i = 0; i < l1; i++)
            countA[A[i] - 'a']++;
         
        for (int i = 0; i < l2; i++)
            countB[B[i] - 'a']++;
 
        // Check if there is a character that
        // appears more than once in A and does
        // not appear in B
        for (int i = 0; i < 26; i++)
            if ((countA[i] > 1 && countB[i] == 0))
                return 'A';
 
        return 'B';
    }
 
    // Driver Code
    public static void Main()
    {
        string a = "abcdea";
        string b = "bcdesg";
    Console.WriteLine(stringPalindrome(a, b));
    }
}
 
// This code is contributed by vt_m.

<?php
// Given two strings, check which string
// makes palindrome first.
 
$MAX_CHAR = 26;
 
// returns winner of two strings
function stringPalindrome($A, $B)
{
    global $MAX_CHAR;
     
    // Count frequencies of characters in
    // both given strings
    $countA = array_fill(0, $MAX_CHAR, 0);
    $countB = array_fill(0, $MAX_CHAR, 0);
    $l1 = strlen($A);
    $l2 = strlen($B);
    for($i = 0; $i < $l1; $i++)
        $countA[ord($A[$i])-ord('a')]++;
    for($i = 0; $i < $l2; $i++)
        $countB[ord($B[$i])-ord('a')]++;
 
    // Check if there is a character that
    // appears more than once in A and does
    // not appear in B
    for ($i = 0 ; $i < 26; $i++)
        if (($countA[$i] > 1 && $countB[$i] == 0))
        return 'A';
 
    return 'B';
}
 
    // Driver Code
    $a = "abcdea";
    $b = "bcdesg";
    echo stringPalindrome($a,$b);
     
// This code is contributed by mits
?>

<script>
 
// javascript program to check which string
// makes palindrome first.
 
 
    var MAX_CHAR = 26;
 
    // returns winner of two strings
    function stringPalindrome(A, B)
    {
        // Count frequencies of characters in
        // both given strings
        var countA = Array.from({length: MAX_CHAR}, (_, i) => 0);
        var countB = Array.from({length: MAX_CHAR}, (_, i) => 0);
 
        var l1 = A.length;
        var l2 = B.length;
         
        for (var i = 0; i < l1; i++)
            countA[A.charAt(i).charCodeAt(0) - 'a'.charCodeAt(0)]++;
         
        for (var i = 0; i < l2; i++)
            countB[B.charAt(i).charCodeAt(0) - 'a'.charCodeAt(0)]++;
 
        // Check if there is a character that
        // appears more than once in A and does
        // not appear in B
        for (var i = 0; i < 26; i++)
            if ((countA[i] > 1 && countB[i] == 0))
                return 'A';
 
        return 'B';
    }
 
    // Driver Code
    var a = "abcdea";
    var b = "bcdesg";
    document.write(stringPalindrome(a, b));
 
// This code is contributed by 29AjayKumar
</script>

A

Complejidad temporal: O(l1+l2)
Espacio auxiliar: O(52) 

Este artículo es una contribución de Akshay Rajput . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.