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

×

STRPALIN - Editorial

1
4

PROBLEM LINK:

Contest
Practice

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

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

setter
tester

This question is marked "community wiki".

asked 13 Mar '16, 14:26

kevinsogo's gravatar image

7★kevinsogo
1.7k583142
accept rate: 11%

edited 27 Mar '16, 22:31


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")
link

answered 15 Mar '16, 15:26

subhendu_m's gravatar image

3★subhendu_m
1
accept rate: 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<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

rohit_0801's gravatar image

5★rohit_0801
3079
accept rate: 10%

****#include<cstring>

include<cstdio>

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??**

link

answered 15 Mar '16, 22:53

deepansh_946's gravatar image

2★deepansh_946
466
accept rate: 0%

include<stdio.h>

include<string.h>

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???????????????????

link

answered 19 Mar '16, 10:48

liliput1992's gravatar image

3★liliput1992
1
accept rate: 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.

link

answered 13 May '16, 11:04

rahulbawa1991's gravatar image

1★rahulbawa1991
1
accept rate: 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

link

answered 13 May '16, 19:04

deepansh_946's gravatar image

2★deepansh_946
466
accept rate: 0%

include<bits stdc++.h="">

using namespace std; int main(){ int t,a,b; cin>>t; string s,s1; while (t--) {b=0; cin>>s>>s1; for (int x=0;x<s.size();++x) {for="" (int="" y="0;y&lt;s1.size();++y)" {="" if="" (s[x]="=s1[y])" {++b;break;}}}="" if="" (b="">0) {cout<<"Yes"<<endl;} else {cout<<"No"<<endl;}} return 0;}

Is This Optimal Solution?

link

answered 31 Jul '16, 21:10

rajat09's gravatar image

3★rajat09
0
accept rate: 0%

edited 31 Jul '16, 21:13

include <stdio.h>

include <stdlib.h>

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.

link

answered 03 Mar '17, 10:50

karthik1's gravatar image

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; }  

link

answered 04 Jul '17, 14:32

arnabfromjec05's gravatar image

2★arnabfromjec05
1
accept rate: 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 <a.length() ; i++) {
            counts[a.charAt(i)-97]++;
            counts[b.charAt(i)-97]++;
        }
        Arrays.sort(counts);
        // If there are more than 1 common element ouput yes else no
        if (counts[counts.length-1]>=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?

link

answered 01 Aug, 20:26

m_corleone_22's gravatar image

1★m_corleone_22
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,038
×1,537
×601
×192
×17

question asked: 13 Mar '16, 14:26

question was seen: 5,476 times

last updated: 01 Aug, 20:26