keep 4 pointers
la, lb ra, rb
la = -1; lb=-1; ra=n; rb=n;
l stands for left side, r stands for right side
a is first char b is second char
int minD( char []a, const int &n, const char &a1, const char &b1)
int i=0;
int j=n-1;
int mind=-1;
while (i<j)
{
bool chkMin = false;
if (a[i] == a1)
{
if ((la==-1) || (lb==-1)){ la=i; chkMin = true;}
}
else if (a[i] == b1)
{
if ((la==-1) || (lb==-1)){ lb=i;chkMin = true;}
}
if (a[j] == a1)
{
if ((ra==-1) || (rb==-1)){ ra=j;chkMin = true;}
}
else if (a[j] == b1)
{
if ((ra==n) || (rb==n)){ rb=j;chkMin = true;}
}
if (chkMin)
{
if ((la !=-1) && (lb != -1)) mind=min(mind, abs(la-lb));
if ((ra !=n) && (rb != n)) mind=min(mind, abs(ra-rb));
if ((la!=-1) &&(rb!=n)) mind=min(mind, abs(la-rb));
if ((lb!=-1) &&(ra!=n)) mind=min(mind, abs(ra-lb));
}
i++;j--;
}
return mind; //returns -1 if both chars not found
}
towards centre
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Fri, Jun 17, 2011 at 11:15 PM, Harshal <[email protected]> wrote:
> Given a character array with a set of characters, there might be
> repetitions as well, given two characters, you should give the minimum
> distance between these two characters in the whole array. O(n) solution is
> required.
>
> --
> Harshal Choudhary,
> III Year B.Tech CSE,
> NIT Surathkal, Karnataka, India.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
