My program is taking so long. How can I make this run fast?

general
1

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

2

@sharmamayank94

Refer my solution. Here’s the link.

3

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 :

  1. take the string as input
  2. declare an empty hashset of characters , and a variable flag as false
  3. for each character in the string :
    1. check whether it exists in the hashset
      If it exists : print “yes” , set flag to true and break
      else : insert it into the hashset
  4. after loop completes , if flag is false print “no”
  5. 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