PROBLEM LINK:Author: Sunny Aggarwal DIFFICULTY:Cakewalk PREREQUISITES:String processing PROBLEM:Given two strings $A$ and $B$, is it possible to choose some non empty strings $s_1$ and $s_2$ such that $s_1$ is a substring of $A$, $s_2$ is a substring of $B$, and $s_1 + s_2$ is a palindromic string? QUICK EXPLANATION:If $A$ and $B$ share a common letter, output EXPLANATION:This problem can be solved with a few simple observations. First, what is the simplest palindrome you can think of? Surely, a single letter word is a palindrome. However, such a palindrome cannot be obtained as $s_1 + s_2$ because $s_1$ and $s_2$ must be nonempty (which means the length of $s_1 + s_2$ is at least two). So the next best thing is a twoletter palindrome, which is just a letter repeated two times. The only way we can form such a palindrome as $s_1 + s_2$ is when $s_1$ and $s_2$ are the same singleletter word. Thus, if $A$ and $B$ share a common letter, then the answer must be But what if $A$ and $B$ don't have a common letter? Well, it turns out that the answer is (The arguments above show that $A$ and $B$ sharing a common letter is both necessary and sufficient for the palindrome $s_1 + s_2$ to exist.) Thus, our solution is really simple: The answer is In the following, we will describe a few methods on how to compute the answer. Finding a common letter: Method 1The easiest way is to simply find two indices $i$ and $j$ such that $A[i] = B[j]$. The following C code demonstrates it:
Each C/C++ note: Even though the problem says $A$ and $B$ are only up to $1000$ in length, you may need to make the char arrays Finding a common letter: Method 2The code above isn't actually the fastest way to compute the answer, because it checks all pairs of indices, and there can be up to $1000000$ such pairs. To compute the answer faster, we can use the fact that all letters are lowercase letters. One way would be to check which of the 26 lowercase letters appear in $A$, and which ones appear in $B$, and find a letter that appears in both. The following Java code shows one way to do it:
It uses the A fancier way of doing the above would be to use a bitmask, or using an integer's bits as a boolean array. The $i$th bit will be on if and only if the $i$th lowercase letter is present in the string. Since there are only 26 characters, only 26 bits are needed, so our mask would be a value between $0$ and $2^{26}  1$. The following C++ code shows how to do it:
It uses the bitwise AND operator to check if the two masks have a common on bit, which only happens if $A$ and $B$ share a common letter. Finally, we can use sets to represent the set of letters of $A$ and $B$. This way, $A$ and $B$ share a common letter if and only if the intersection of their letter sets is nonempty. The following Python code shows one way to do it:
It uses the fact that Python sets use the operator
Time Complexity:$O(AB)$ or $O(A + B)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 13 Mar '16, 14:26

Here is a simple Python implementation in 10 lines. Please provide your comments on it.
answered 15 Mar '16, 15:26

import java.util.; import java.lang.; import java.io.*; class Rohit { public static void main (String[] args) throws java.lang.Exception { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t>0) { byte flag=0; String a=sc.next(); String b=sc.next(); String ch[]=a.split(""); for(int i=0;i<ch.length;i++) { if(b.contains(ch[i])) { flag=1; break; } } if(flag==1) System.out.println("Yes"); else System.out.println("No"); } } } //Have a look at my Solution.It also works in O(A).
link
This answer is marked "community wiki".
answered 15 Mar '16, 21:37

****#include<cstring> include<cstdio>include<iostream>using namespace std; int main() { int t; scanf("%d",&t);
} Why it is giving wrong ans??** answered 15 Mar '16, 22:53

include<stdio.h>include<string.h>define gc getchar_unlockedint inp() { char c = gc(); while(c<'0'  c>'9') c = gc(); int ret = 0; while(c>='0' && c<='9') { ret = 10 * ret + c  48; c = gc(); } return ret; } int main() { int a1[26]={0},a2[26]={0},t; t=inp(); while(t) { char x1[1001],x2[1001],dump; scanf("%s%s",x1,x2);
return 0; } why is this code giving wrong ans??????????????????? answered 19 Mar '16, 10:48

S1 and S2 to form a new palindrome, both of them must contain equal frequencies of each word that they contain. Is it a valid solution too ? PS: I understand that this would take more time than the solution mentioned above. answered 13 May '16, 11:04

@rahulbawa1991 I submitted the solution with the same logic as you are saying but it showed WA. Here is my code > https://www.codechef.com/viewsolution/9610230 answered 13 May '16, 19:04

include <stdio.h>include <stdlib.h>include <string.h>int main() {
} //please find the loophole in this solution. answered 03 Mar '17, 10:50

sir i did the same method of counting frequencies and comparing but it showing some error like this 2 6 NA RE (SIGSEGV) (0.000000) 2 7 NA RE (SIGSEGV) (0.000000) my code is include<iostream>using namespace std; int main() { int t; cin>>t; while(t) { int a[26]={0},b[26]={0}; char s1[101],s2[101]; cin>>s1>>s2; int i=0,j=0; while(s1[i]!='\0') { a[s1[i]'a']++; i++; } while(s2[j]!='\0') { b[s2[j]'a']++; j++; } i=0; while(i<26) { if(a[i]>0&&b[i]>0) break; i++; } if(i==26) cout<<"No"; else cout<<"Yes"; cout<<endl; } return 0; } answered 04 Jul '17, 14:32

class Solution {
} I am getting runtime error please help.! what am I doing wrong? answered 01 Aug '18, 20:26

Here is a C++ solution using maps. answered 18 Nov '18, 13:40
