ALPHABET - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Sergey Kulik
Tester: Harshil Shah
Editorialist: Pawel Kacprzak

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Strings, Implementation

PROBLEM:

For a fixed set of Latin letters S, for each of given N words decide if it can be formed using only letters from S.

QUICK EXPLANATION:

For each of given words, check if all its letters are in the given set of known letters S by iterating over letters in S explicitly or using any data structure with fast lookup operation.

EXPLANATION:

Subtask 1

In the first subtask, the set S contains exactly one letter. In this case, it is very easy to decide if a given word can be formed using only letters from S, because there is only one letter that can be used, so for example if the letter in S is c, then all possible words that can be written using it are: c, cc, ccc, …. Since the length of any word in the input can be at most 12, then there are exactly 12 different words for which the answer is "Yes". For all other words the answer is “No”, because each of them contains at least one letter not in S.

Subtask 2

In the second subtask, S can contain at most 26 letters. In this case, for a given input word W, we want to check if all its letters are in S. In order to do that, we can iterate over all letters of W and for each one check if it is in S. Since S is very small, that check can be performed actually by iterating over all letters in S explicitly. The answer is “Yes” if all letters of W are in S, otherwise the answer is “No”. Thus, for a single word W, the answer can be computed in O(|W| * |S|) time, so the total running time is O(|total_len|*|S|), where total_len is the sum of lengths of all N words in the input.

For a faster solution, first we can store letters from S in any data structure that provides fast lookup - array will work the best here, since there are at most 26 different letters, but hash table is also fine here. If array is used this step building the array takes O(|S|) time. Then, for a given input word W, we can check if all of its letters are in S using the lookup in our data structure. It follows that the total running time of this method is O(|S|+|total_len|), where total_len is the sum of lengths of all N words in the input.

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester’s solution can be found here.
Editorialist’s solution can be found here.

2

Another solution can be sort every word and equate it with input word instead of checking occurrence of each letter.
For example if input string is “chef”–after sorting–“cehf”.

Assume input sting be “cfeh”, after sorting it will also become “cehf” which is equal to sorted string of previous input.

3

Sorting also takes time…(nlogn)

4

I want to know whats wrond with my solution. CodeChef did not accept this solution.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class Jeff
{
public static void main(String args[])throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println(“ENTER LETTERS THAT JEFF CAN READ”);
String jVoc=br.readLine();
System.out.println(“ENTER NUMBER OF WORDS IN THE BOOK”);
int num=Integer.parseInt(br.readLine());
String word;
for(int i=1;i<=num;i++)
{
System.out.println("ENTER WORD "+i);
word=br.readLine();
boolean canRead=true;
for(int j=0;j<=jVoc.length()-1;j++)
{
char ch=jVoc.charAt(j);
if(word.indexOf(ch)==-1)
{
canRead=false;
break;
}
}
if(canRead==true)
System.out.println(“YES”);
else System.out.println(“NO”);
}

}

}

5

#include<stdio.h>
int main()
{
char s[27];
scanf("%s",s);
int n;
scanf("%d",&n);
while(n>0)
{
char ch[13];
scanf("%s",ch);
int count=0,i,j;
for(i=0;ch[i]!=’\0’;i++)
{
for(j=0;s[j]!=’\0’;j++)
{
if(ch[i]==s[j])
{
count++;
break;
}
}
}
one:
if(count==i)

		printf("YES\n");
	else
		printf("NO\n");
	n--;
}

return 0;
}

what is wrong in this code can anyone help me plz

6

@alphajazz-

The first glaring error I saw was that code printed “YES” and “NO” instead of “Yes” or “No”

Fix that and try again :slight_smile:

7

My approach was to put the given letters into a set and then take union for every new word

If the length of union set equals the length of given letters then ‘Yes’ else ‘No’

8

Hi… I got output still if i try to submit its showing wrong answer…Can anyone please help me to fix this issue… Here is my code.

checkString=input();

testCase=int(input());

for i in range (testCase):

inputString=input();

count=0;

for i in range(0,len(inputString)):

if inputString[i] in checkString:

&nbsp         count+=1;

if(count==len(checkString)):

print(“Yes”);

else:

print(“No”);

9

@aniesta

Codechef doesn’t want you to type all those display messages in your program.
Just remove those lines and print only the answer.

10

Hello everyone ,
I am getting a wrong ans .
please help
Here is my work
#include <stdio.h>
#include <string.h>
int main()
{
int t,len1,len2;
char arr[27];
//scanf("%d",&n);
scanf("%s",arr);
len1= strlen(arr);
scanf("%d",&t);
while(t–)
{
char arr2[13];
int flag=0;
len2= strlen(arr2);
scanf("%s",arr2);
for(int i=0;i<len2;i++)
{
for(int j=0;j<len1;j++)
{
if(arr2[i]==arr[j])
{
flag++;
break;
}
}
}

	if(flag==len2)
		printf("Yes\n");
	else
		printf("No\n");
}

}