#include <stdio.h>
using namespace std;
int main()
{
char *j= new char [25];
int z=0;
while (z==0)
{
scanf("%24s",j);
bool check=0;
for (int n=0, i=n+1; j[n]!=’\0’; n++, i=n+1)
{
for(; j[i]!=’\0’; i++)
if(j[n]==j[i])
{
printf("Yes\n");
check=1;
break;
}
if(j[n]==j[i])
break;
}
if(check!=1)
printf(“No\n”);
}
delete[]j;
return 0;
}
@sharmamayank94
Refer my solution. Here’s the link.
The problem with your code it that it is running in O(n^2) time. You can use a hashset (called unordered set in c++ STL) to easily do this in O(n) time . I don’t know much c++ so I will write you a pseudocode of how you can do it :
- take the string as input
- declare an empty hashset of characters , and a variable flag as false
- for each character in the string :
- check whether it exists in the hashset
If it exists : print “yes” , set flag to true and break
else : insert it into the hashset
- after loop completes , if flag is false print “no”
- done
How is this O(n) ? basically it makes use of the fact that checking and insertion in hashset is O(1) , and you will be using one/both of these operations per character of the string.
To use a hashset in c++ you can use the STL , or if the strings consist of only ascii characters you can easily do it using a single array.
I would definitely recommend you to look into hashsets and hashmaps as these are very powerful and much useful in programming contests.
You can read up on unordered sets in C++ STL from this link