How to deal with time limit exceeded in this case?

Question

0.00/5 (No votes)

See more:

question is to find no of common characters in n strings.

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N
N
lines follow. For each i (1≤i≤N), the i-th of these lines contains a single string Si.

Constraints

1≤T≤1,000
1≤N≤1,000
1≤|Si|≤200

for each valid i
S1,S2,…,SN
contain only lowercase English letters
The sum of length of strings over all test cases ≤ 3500000

What I have tried:

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

int main() {
    int t;
    cin>>t;
    while(t--)
    {
	int n;
	cin>>n;
	if(n==1)
	{cin.ignore();
	    string s;
	    getline(cin,s);
	    int k=s.length();
	    cout<<k<<"\n";
	}
	else
	{
	int i,ctr=0;
	bool c[26];
	memset(c,true,sizeof(c));
	cin.ignore();
	while(n--)
	{
	     string s;
	     getline(cin,s);
	     bool a[26]={false};
	     
	     for(i=0;i<s.length();i++)
	     a[s[i]-'a']=true;
	    
	     for(i=0;i<26;i++)
	     if(a[i]!=c[i])
	      c[i]=false;
	}
	for(i=0;i<26;i++)
	if(c[i]==true)
	ctr++;
	cout<<ctr<<"\n";
	}
    }
	return 0;
}

Posted 7-Feb-19 4:08am

Prateek Krishna

Updated 7-Feb-19 10:42am

Rick York

v2

Add a Solution

Comments

ZurdoDev 7-Feb-19 10:30am

What is your question?

Prateek Krishna 7-Feb-19 10:35am

it is showing time limit exceeded...
How to deal with it?

Rick York 7-Feb-19 10:38am

Write code that runs faster.

Prateek Krishna 7-Feb-19 10:40am

can you give some tips regarding this code to deal with TLE

Rick York 7-Feb-19 11:29am

You could start by getting all of your input from a file instead of cin. You just have to use a different stream other than cin, one you have opened yourself. You should always do this when you can because it is much easier to build test cases that you can use over and over. You can have multiple files for different tests and switch between them easily too.

Richard MacCutchan 7-Feb-19 10:51am

These exercises are largely a waste of time. Get hold of a good C++ book and learn the language in detail.

Rick York 7-Feb-19 11:24am

I agree fully! Too bad I can't give this comment a rating. ;)

Richard MacCutchan 7-Feb-19 11:28am

Thanks, but not to worry; points don't make prizes here. :)

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2019-02-07T05:18:00

Solution 1

Quote:
How to deal with time limit exceeded in this case?

Simple, you need to find a more efficient algorithm that solve the problem.
You need to understand where your program spend time and thing if another way can be faster.
the tool to see how program spend time is a program profiler.

Posted 7-Feb-19 5:18am

Patrice T

Dave Kreskowiak · Answer 2 · 2019-02-07T05:45:00

These challenges are written to get you to really think about different solutions to the problem.

If you just go and code up the easy, straight-forward algorithm to solves the problem, your code will work, but will always fail the time limit.

You have to scrap this code and rethink how you attack the problem as described.

No, I'm not giving you an algorithm to solve the problem because that would be ME thinking about how to solve the problem and not YOU thinking about it, and that's the entire point of those challenges.

CPallini · Answer 3 · 2019-02-07T10:42:00

Try with C++

C++

#include <iostream>
#include <array>
#include <set>
#include <algorithm>

using namespace std;

int main()
{
  size_t T;
  cin >> T;
  for (size_t t = 0; t<T; t++)
  {
    size_t N;

    cin >> N;
    cin.ignore();

    array<size_t, 26> occur{0};
    for (size_t n = 0; n< N; ++n)
    {
      string line; 
      getline(cin, line);
      set<char> s;
      for (auto c : line)
        s.insert(c); 
      for ( auto c : s)
        occur[c-'a']++;
      }
    }
    size_t common = count_if(occur.begin(),  occur.end(), [N](size_t x){return x == N;});
    cout << common << "\n";
  }
}

How to deal with time limit exceeded in this case?

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0