 # Getting TLE with passing strings and substrings into a function

Hii!!
I am getting TLE when I pass a string and its substring’s bounds (low,high) into a function.
And its running good when passing it as a substring.

Here is accepted function…

`````` ll func(string s,char c)
{
ll n=s.size(); ll mid=n/2;
if(n==1) return (s!=c);
ll m1=0,m2=0;
for(ll i=0;i<mid;i++) m1+=(s[i]==c);
for(ll i=mid;i<=n-1;i++) m2+=(s[i]==c);
ll c1=func(string(s.begin(),s.begin()+mid),c+1);
ll c2=func(string(s.begin()+mid,s.end()),c+1);
return min(n/2-m2+c1,n/2-m1+c2);
}
``````

And here is TLE function…

``````ll func(string s,ll low,ll high,char c)
{
ll n=high-low+1; ll mid=(high-low)/2+low;
if(low==high) return (s[low]!=c);
ll m1=0,m2=0;
for(ll i=low;i<=mid;i++) m1+=(s[i]==c);
for(ll i=mid+1;i<=high;i++) m2+=(s[i]==c);
return min(n/2-m1+func(s,mid+1,high,c+1),n/2-m2+func(s,low,mid,c+1));
}
``````

As you can see, the only difference is passing the string.
Please refer to both solutions if any confusion arises…

Can anyone please tell me what I am missing?

NOTE: If this is a problem is related to inline code, please tell me about it as I am not getting how this all is working. Your function is making a fresh copy of string each recursive call, you should pass string by reference.

``````ll func(string &s,ll low,ll high,char c)
{
ll n=high-low+1; ll mid=(high-low)/2+low;
if(low==high) return (s[low]!=c);
ll m1=0,m2=0;
for(ll i=low;i<=mid;i++) m1+=(s[i]==c);
for(ll i=mid+1;i<=high;i++) m2+=(s[i]==c);
return min(n/2-m1+func(s,mid+1,high,c+1),n/2-m2+func(s,low,mid,c+1));
}
``````

Notice the pass by reference:

``````ll func(string &s ....)
``````

https://codeforces.com/contest/1385/submission/87204689

2 Likes

Hii… @dardev thank you so much for your reply. I have understood what you are trying to say. But why did this thing not make an effect in submission 1? Was this because I created a substring?

Passing whole copies of a string is more expensive than passing part copies of string. But both perform worse than passing string by reference.

1 Like

Okay I got it. Thanks