STONES - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

This was the easiest problem of the contest. All one had to was to move over all characters is S and check if they were present in J as well. Checking could be done either by iterating over all character of J which takes time O(|J|) or by keeping an array/hashset for O(1) look up.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like

#include<stdio.h>
#include<string.h>
#define MAX 200

int main()
{
int t,j,s,i;
char je[100],st[100];
scanf("%d",&t);
while(t)
{
int h[MAX]={0};
int c=0;
scanf("%s",je);
scanf("%s",st);
j=strlen(je);
s=strlen(st);
for(i=0;i<j;i++)
h[je[i]]=je[i];
for(i=0;i<s;i++)
{
if(st[i]==h[st[i]])
c++;
}
printf("%d\n",c);
t–;
}
return 0;
}

what is wrong with this answer i dont understand i tried it on my computer and got the answers but here i am getting wrong answer

@rusfian

Your code works all fine EXCEPT for 1 category of corner case.

Try changing string length to 101 and see the magic :slight_smile:

Here is the test case at str length of 100-

 pre< 
 input
        1
        bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
        aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab   >
Output-

100

The reason that the error occurs is that the end of string is taken up by position c, so there is nothing to denote end of line or end of string, and hence it continues taking the other “aaaaaa…” as input of string 1.

This results in string 2 being an empty string, and for it the condition is always true.

Its an abnormal behaviour, and hence 1 extra character is always recommended.

(Tested code by asking it to print je[101]…je[110] and got the chars of next line in it. Hence the above theory)

import java.util.;
import java.lang.
;

class jewels
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int tc,i,len1,len2,j,k;
tc = sc.nextInt();
int count[] = new int[tc];
for(i=0;i<tc;i++)
{
StringBuffer jewels = new StringBuffer(sc.next());
StringBuffer stones = new StringBuffer(sc.next());

        len1 = jewels.length();
        len2 = stones.length();
        for(j=0;j<len1;j++)
        {
            for(k=0;k<stones.length();k++)
            {
                if(stones.charAt(k)==jewels.charAt(j))
                {
                    count[i]++;
                    stones.deleteCharAt(k);
                    break;
                }
            }
        }
    }
    for(i=0;i<tc;i++)
        {
            System.out.println(count[i]);
        }
}

}
Can someone tell me whats wrong with this?

stones.deleteCharAt(k);

is this line really required? Try submitting without this, I guess this seems to be the problem

1 Like

@yyash

I believe that you don’t have to delete the characters of stone. Meaning, multiple isntances of that stone occurring has to be counted. Your code fails in the following test cases-

Input
1
abc
aaa

Output
1

Expected Output-
3

Yes, @shraeyas is right. I too don’t feel that the line is required.

Isn’t the code giving compilation error?

Its actually because of how the code is pasted here by him. I had to do corrections to resume checking…you can say I got experience of this now XD (since its a problem with >75% of codes copy pasted here)

Thank you. Misunderstood the logic of the question

@yyash here’s the working code.

I modified your code a bit. PLease compare it with your original code.

And yes you don’t have to use that count array to display the results of test cases all at once. You can output the results of each test case one by one. And try using ideone next time to share codes

:smiley:

1 Like

plz check my code as i am getting all cases right

import java.util.Scanner;
class codechef
{
public static void main(String[] args)
{
Scanner kb=new Scanner(System.in);
	int test=kb.nextInt();
	while(test-->0)
{
String s1=kb.next();
		String s2=kb.next();
		int ans=0;
		for(int i=0;i<s1.length();i++)
		{
			for(int j=i;j<s2.length();j++)
			{
				if(s1.charAt(i)==s2.charAt(j))
				ans++;
			}
		}
		System.out.println(ans);

``}

``}
`}

If anyone who doesn’t know much about hashset or any data structure , u can go do this ques by using simple brute force .U can go through my code.
https://www.codechef.com/viewsolution/15487815
If u have any issue feel free to share.

//what is the problem in this programme.
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
int main()
{
int t,i,k,a;
string s,j;
cin>>t;

while(t--)
{
	cin>>j>>s;
	int p=0;
	for(i=0;j[i]!='\0';i++)
	{
		for(k=0;s[k]!='\0';k++)
		{
			if(j[i]==s[k])
			{
				p++;
				s[k]='{';
				break;
			}
		}
	}

	cout<<p<<"\n";
}

return 0;

}

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

int main()
{
int t;
cin>>t;
while(t–)
{
string s1,s2;
cin>>s1>>s2;
int a[128]={0};
int b[128]={0};
int x=128,l1=s1.length(),l2=s2.length();
for(int i=0;i<l1;i++)
{
a[s1[i]-’\0’]++;
}
for(int i=0;i<l2;i++)
{
b[s2[i]-’\0’]++;
}
int c=0;
bool k[128]={false};
for(int i=0;i<l2;i++)
{
if(b[s2[i]-’\0’]>0&&a[s2[i]-’\0’]>0&&!k[s2[i]-’\0’])
{
c+=b[s2[i]-’\0’];
k[s2[i]-’\0’]=true;
}
}
cout<<c<<endl;
}
return 0;
}

I tried to solve it using longest common subsequence method. I failed to realise my error. Can someone please point it out? My code is:

import java.util.*;

public class Main {
	
	
	
	public static int LongestCommonSubsequence (String str1, String str2)
	{
		int size1 = str1.length();
		int size2 = str2.length();
		
		int [] [] arr = new int [size1+1][size2+1];
		
		for(int j=0;j<size2+1;j++)
		{
			arr[0][j] = 0;
		}
		for(int i=1;i<size1+1;i++)
		{
			arr[i][0] = 0;
		}
		for(int i=1;i<size1+1;i++)
		{
			for(int j=1;j<size2+1;j++)
			{
				if(str1.charAt(i-1)==str2.charAt(j-1))
				{
					arr[i][j] = 1 + arr[i-1][j-1];
				}
				else
				{
					arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);
				}
			}
		}
		return arr[size1][size2];
	}
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		while(test!=0)
		{
			String str1 = sc.next();
			String str2 = sc.next();
			System.out.println(LongestCommonSubsequence(str1,str2));
			test--;
		}
	}
}