### Ryuma_7810's blog

By Ryuma_7810, history, 4 months ago,

Problem: https://mirror.codeforces.com/contest/1937/problem/B (Binary path)

int n;  cin>>n;
string s,t; cin>>s>>t;

int count=1;
string path= s[0] + t;
string min_str= path;

for(int i=1; i<n; i++)
{
path[i]= s[i];

if(path < min_str){
count=1;
min_str= path;
}
else if(path == min_str)
count++;

}

cout<<min_str<<endl;
cout<<count<<endl;


I have written this coder sample for the above problem, but it keeps on getting TLE on Test 4. I can't seem to understand it because the time complexity for this is O(n) and n<=2.10^5 Can you explain in which part of my code is there an issue ? I want to use this current approach.

• 0

 » 4 months ago, # | ← Rev. 2 →   +4 String comparison has O(n) complexity, therefore your solution has O($n^2$) complexity, not O(n).If you really want to keep the current approach, then make an observation about the condition when one string is smaller than other, and use hashing for the comparison of their equality, but I recommend thinking about something else.
•  » » 4 months ago, # ^ |   0 Thanks for the clarification
•  » » » 4 months ago, # ^ |   0 You're welcome
 » 3 months ago, # |   0 no