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

×

ALPHABET - Editorial

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.

This question is marked "community wiki".

asked 27 Aug '16, 02:55

pkacprzak's gravatar image

5★pkacprzak ♦♦
74485097
accept rate: 12%

edited 27 Aug '16, 22:32

admin's gravatar image

0★admin ♦♦
19.8k350498541


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.

link

answered 30 Aug '16, 19:26

swamicoder's gravatar image

4★swamicoder
2347
accept rate: 10%

Sorting also takes time...(nlogn)

link

answered 30 Aug '16, 22:29

vivek96's gravatar image

2★vivek96
533220
accept rate: 8%

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

}

}

link

answered 14 Sep '16, 17:10

aneista's gravatar image

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

link

answered 04 Mar '17, 20:31

alphajazz's gravatar image

2★alphajazz
1
accept rate: 0%

@alphajazz-

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

Fix that and try again :)

link

answered 04 Mar '17, 22:59

vijju123's gravatar image

4★vijju123 ♦♦
15.4k12066
accept rate: 18%

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'

link

answered 22 Apr '17, 17:24

krshubham's gravatar image

3★krshubham
1
accept rate: 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:
       &nbsp         count+=1;
             if(count==len(checkString)):
                 print("Yes");
             else:
                 print("No");

link
This answer is marked "community wiki".

answered 10 Jan '18, 15:40

jayanthi154's gravatar image

0★jayanthi154
1
accept rate: 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.

link

answered 14 Jan '18, 20:11

malcolm_123ssj's gravatar image

3★malcolm_123ssj
373
accept rate: 25%

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

}

link

answered 23 Jan '18, 22:18

anmol_9557's gravatar image

2★anmol_9557
1
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,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