×

# ALPHABET - Editorial

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

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:

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.

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.

This question is marked "community wiki".

74485097
accept rate: 12%

19.8k350498541

 0 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. answered 30 Aug '16, 19:26 234●7 accept rate: 10%
 0 Sorting also takes time...(nlogn) answered 30 Aug '16, 22:29 2★vivek96 533●2●20 accept rate: 8%
 0 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"); } }  } answered 14 Sep '16, 17:10 0★aneista 1 accept rate: 0%

# 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

1
accept rate: 0%

 0 The first glaring error I saw was that code printed "YES" and "NO" instead of "Yes" or "No" Fix that and try again :) answered 04 Mar '17, 22:59 15.4k●1●20●66 accept rate: 18%
 0 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' answered 22 Apr '17, 17:24 1 accept rate: 0%
 0 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:                  count+=1;              if(count==len(checkString)):                  print("Yes");              else:                  print("No"); link This answer is marked "community wiki". answered 10 Jan '18, 15:40 1 accept rate: 0%
 0 @aniesta Codechef doesn't want you to type all those display messages in your program. Just remove those lines and print only the answer. answered 14 Jan '18, 20:11 37●3 accept rate: 25%

# 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");
}


}

1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

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,639
×1,646
×825
×349
×28
×3

question asked: 27 Aug '16, 02:55

question was seen: 3,819 times

last updated: 23 Jan '18, 22:18