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

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

}

11

#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin>>s;
int n;
cin>>n;
string w;
for(int i=0;i<n;i++)
{
int flag=0;
cin>>w;
for(int i=0;i<s.length();i++)
{
for(int j=0;j<w.length();j++)
{
if(s[i]==w[j])
{
flag=0;
break;
}
else
{
flag=1;
}
}
}
if(flag==1)
cout<<“No”<<endl;
else
cout<<“Yes”<<endl;
}
}

what is wrong with solution can anyone help me?

12

I hope this will Help You alot :
Just Go Through this

And Subscribe my channel Hello World Please.

13

can anyone tell me what is wrong with this code

#include <iostream>

using namespace std;



int main() {
	string jStr;
	int a[26]={0};
	cin>>jStr;
	for(int i=0;i<jStr.length();i++)
	{
		int j=(int)jStr[i]-97;
		a[j]=1;
	}
	int no;
	cin>>no;
	string str;
	int notPresent{0};
	while(no--)
	{
		cin>>str;
		for(int j=0;j<str.length();j++)
		{
			int temp=(int)str[j]-97;
			if(a[temp]==1)
			{
			    notPresent=0;
			}
				
			else
			{
				notPresent++;
			}
		}
		if(notPresent>0)
			cout<<"No"<<endl;
		else
			cout<<"Yes"<<endl;
	}
	
	return 0;
}

i have tested it with provided example

14

help with this code
#include
#include
using namespace std;

int main()
{

    string s;
    cin >> s;
    sort( s.begin(), s.end() );
    int n;
    cin >> n;
    while( n-- )
    {
        string s1;
        cin >> s1;
        sort( s1.begin(), s1.end() );
        if ( s == s1 )
        cout << "Yes" << endl;
        else
        cout << "No" << endl;
    }
    
return 0;

}

15

PLEASE CHECK MY CODE ONCE:
My almost all custom inputs are working well and giving out correct solutions, but while SUBMITTING its providing WRONG ANSWER

#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 
  string  s , t1;
  cin >> s;
  int j , n = s.length(); 
  char char_array[n + 1]; 

   strcpy(char_array, s.c_str()); 
   int t , i;
   cin >> t;
   for( i = 0 ; i < t ; i++ )
   {
      cin>>t1;
      int k = t1.length();
      char char_array2[k + 1]; 
      strcpy( char_array2, t1.c_str() );
      int m , a = 0;
      for( j = 0 ; j < = k ; j++ )
      {
        for( m = 0 ; m < = n ; m++ )
        {
            if( char_array2[j] == char_array[m] )
           {
                a++;
            }
        }
    }
    if(a!=n+1)
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
  }
return 0;
}

Waiting for a soon REPLY!

16

#include<bits/stdc++.h>
using namespace std;

int main(){
string s;
getline(cin, s);
int st[26]={0};
for(int i=0; i<s.length(); i++){
st[(int)s[i]- 97]=1;
}
int n;
scanf("%d", &n);
while(n–){
string w; int c=0;
getline(cin, w); //##############This line############//
for(int i=0; i<w.length(); i++){
if(st[(int)w[i]- 97]==1){
++c;
}
}
if(c==w.length()) printf(“Yes\n”);
else printf(“No\n”);
}

}

In the above code, there’s a line marked “This line”. If I am using getline, my code was not accepted, but when I used cin, my code was accepted. Any idea why this happened?

17

in the 5th line you have left Ampersand …on scanf line .same mistake in while loop 3rd line “&ch”

18

#include<bits/stdc++.h>

#define ll long long

#define lli long long int

#define MOD 1000000007

#define input(a) cin >> a

#define print(a) cout << a

#define printsp(a) cout << a << " "

#define println(a) cout << a << endl

#define debug(a) cout << #a << " = " << a << “\n”

#define testCases int t; cin >> t; while(t–)

#define loop(n) for(ll int i = 0; i < n; i++)

#define iloop(k,n) for(ll int i = k; i < n; i++)

#define jloop(k,n) for(ll int j = k; j < n; j++)

#define reverseLoop(k,n) for(ll int i = k; i >= n; i–)

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace std;

void solution(){

string s, word;

input(s);

int n;

input(n);



loop(n){

    bool flag = 1;

    input(word);

    set <char> letters ( begin(word), end(word) );

    

    for(auto it : letters){

        if(count(s.begin(), s.end(), it) == 0){

            flag = 0;

        }

    }

    println((flag ? "Yes": "No"));

}

}

int main(){

fastIO;

solution();



return 0;

}

1 Like
19

you’re wrong, what if the string is “pepsi”
and the ones to check for are “peppsi”,“peepsi”
They’re correct but your method will fail here :slight_smile:

20

#include <bits/stdc++.h>

using namespace std;

int main()

{

int t;

string s, s1;

cin >> s;

sort(s.begin(), s.end());

cin >> t;

while (t--)

{

    cin >> s1;

    sort(s1.begin(), s1.end());

    int count = 0;

    for (int i = 0; i < s.size(); i++)

    {

        if (s[i] == s1[i])

        {

            count++;

        }

    }

    if (count == s1.size())

    {

        cout << "Yes" << endl;

    }

    else

    {

        cout << "No" << endl;

    }

}

return 0;

}

//what’s wrong in my code why sort() was not working?