Getting TLE with passing strings and substrings into a function

general
1

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[0]!=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. :expressionless:

2

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 ....)
2 Likes
3

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?

4

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
5

Okay I got it. Thanks