You are not logged in. Please login at www.codechef.com to post your questions!

×

# STRPALIN - Editorial

Author: Sunny Aggarwal
Tester: Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

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 Yes. Otherwise, output No.

# 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 two-letter 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 single-letter word. Thus, if $A$ and $B$ share a common letter, then the answer must be Yes.

But what if $A$ and $B$ don't have a common letter? Well, it turns out that the answer is No. This is because in any palindrome, the first and last letter must be the same. So suppose we can form the palindrome $s_1 + s_2$. Since the first letter belongs to $s_1$ (and thus to $A$) and the last letter belongs to $s_2$ (and thus to $B$), it means that $A$ and $B$ must have a letter in common!

(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 Yes if $A$ and $B$ share a common letter, otherwise, the answer is No.

In the following, we will describe a few methods on how to compute the answer.

# Finding a common letter: Method 1

The easiest way is to simply find two indices $i$ and $j$ such that $A[i] = B[j]$. The following C code demonstrates it:

#include <stdio.h>

char A[1111];
char B[1111];
int main() {
int cases, cas, i, j, good;
scanf("%d", &cases);
for (cas = 1; cas <= cases; cas++) {
scanf("%s%s", A, B);
int good = 0;
for (i = 0; A[i]; i++) {
for (j = 0; B[j]; j++) {
if (A[i] == B[j]) {
good = 1;
break;
}
}
if (good) {
break;
}
}
puts(good ? "Yes" : "No");
}
}


Each for loop iterates through every character of every string. If a common letter is found (A[i] == B[j]), then we mark good as 1 and break out of both loops (using two break statements).

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 A and B at least $1001$ in length, because you need to allocate space for the null terminator.

# Finding a common letter: Method 2

The 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:

import java.util.Scanner;
public class Main {
public static void main (String args[]) {
Scanner sc = new Scanner(System.in);
int cases = sc.nextInt();
boolean aHas[] = new boolean[256];
boolean bHas[] = new boolean[256];
for (int cas = 1; cas <= cases; cas++) {
String a = sc.next();
String b = sc.next();
boolean good = false;
for (char c = 'a'; c <= 'z'; c++) {
aHas[c] = bHas[c] = false;
}
for (int i = 0; i < a.length(); i++) aHas[a.charAt(i)] = true;
for (int i = 0; i < b.length(); i++) bHas[b.charAt(i)] = true;
for (char c = 'a'; c <= 'z'; c++) {
if (aHas[c] && bHas[c]) {
good = true;
break;
}
}
System.out.println(good ? "Yes" : "No");
}
}
}


It uses the aHas and bHas boolean arrays to store which letters appear in which string. The final loop finds a letter "c" such that aHas[c] and bHas[c] are simultaneously true.

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:

#include <iostream>
using namespace std;

int main() {
int cases;
cin >> cases;
while (cases--) {
string a, b;
cin >> a >> b;
int a_mask = 0, b_mask = 0;
for (int i = 0; i < a.size(); i++) a_mask |= 1 << a[i] - 'a';
for (int i = 0; i < b.size(); i++) b_mask |= 1 << b[i] - 'a';
cout << (a_mask & b_mask ? "Yes" : "No") << endl;
}
}


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:

cases = int(raw_input())
for cas in xrange(cases):
a_set = set(raw_input().strip())
b_set = set(raw_input().strip())
print "Yes" if a_set & b_set else "No"


It uses the fact that Python sets use the operator & for set intersection. Another bonus with this solution is that it also works even if letters are not restricted to lowercase letters! Also, such solutions can be reduced to just one line (in Python at least):

for cas in xrange(input()): print "Yes" if set(raw_input()) & set(raw_input()) else "No"


# Time Complexity:

$O(|A||B|)$ or $O(|A| + |B|)$

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

asked 13 Mar '16, 14:26

1.7k586142
accept rate: 11%

 0 Here is a simple Python implementation in 10 lines. Please provide your comments on it. n = int(input()) for i in range(n): a = str(input()).strip() b = str(input()).strip() seta = set([c for c in a]) setb = set([c for c in b]) if len(seta) == len(seta-setb) : print("No") else: print("Yes")  answered 15 Mar '16, 15:26 1 accept rate: 0%
 0 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

****#include<cstring>

# include<iostream>

using namespace std; int main() { int t; scanf("%d",&t);

while(t--)
{
char a[1003],b[1003];
int count,count1,k=0,j,i;
scanf("%s",&a);
scanf("%s",&b);
for(char c='a';c<='z';c++)
{
count=0;
count1=0;
for(j=0,i=0;b[j]!='\0',a[i]!='\0';j++,i++)
{
if(a[i]==c)
{
count++;
}
if(b[j]==c)
{
count1++;
}

}
if(count>=1 && count1>=1 && count==count1)
k++;
}
if(k<=strlen(a) && k<=strlen(b) && k>0)
cout<<"Yes\n";
else
cout<<"No\n";
}
return 0;


} Why it is giving wrong ans??**

answered 15 Mar '16, 22:53

466
accept rate: 0%

# define gc getchar_unlocked

int 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);

    int flag=0,i;
for(i=0;i<strlen(x1);i++)  a1[(x1[i]-'a')]++;

for(i=0;i<strlen(x2);i++)   a2[(x2[i]-'a')]++;

for(i=0 ; i<26 ; i++)
{
if(a1[i]>0 && a2[i]>0)
{
printf("Yes\n");
flag++;
break;
}
}
if(flag==0)
printf("No\n");

memset(a1,0,26);
memset(a2,0,26);
}


return 0; }

why is this code giving wrong ans???????????????????

answered 19 Mar '16, 10:48

1
accept rate: 0%

 0 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 1 accept rate: 0%
 0 @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 46●6 accept rate: 0%

# include <string.h>

int main() {

int n,flag,i=0,j=0;
char a[1001],b[1001];
scanf("%d",&n);
int arr[n];
for(flag=0;flag<n;flag++)
{
scanf("%s",a);
scanf("%s",b);
for(i=0;i<strlen(a);i++){
for(j=0;j<strlen(b);j++){
if(a[i]==b[j]){
arr[flag]=1;
break;
}
}
if(arr[flag]==1) break;
else
arr[flag]==0;
}

}
for(flag=0;flag<n;flag++){
if(arr[flag]==1)
printf("YES\n");
else printf("NO\n");}
return 0;


}

//please find the loophole in this solution.

answered 03 Mar '17, 10:50

1★karthik1
1
accept rate: 0%

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

1
accept rate: 0%

 0 class Solution { public static void main(String[] args) throws IOException { FastInput input = new FastInput(); final StringBuilder stringBuilder = new StringBuilder(); int t = input.nextInt(); int[] counts ; while (t-- > 0) { String a = input.nextLine().toLowerCase(); String b = input.nextLine().toLowerCase(); counts = new int[26]; for (int i = 0; i =2) stringBuilder.append("Yes").append("\n"); else stringBuilder.append("No").append("\n"); } System.out.println(stringBuilder); }  } I am getting runtime error please help.! what am I doing wrong? answered 01 Aug '18, 20:26 1●1 accept rate: 0%
 0 Here is a C++ solution using maps. https://www.codechef.com/viewsolution/21640211 answered 18 Nov '18, 13:40 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,498
×1,615
×630
×192
×17

question asked: 13 Mar '16, 14:26

question was seen: 5,716 times

last updated: 18 Nov '18, 13:40