suppose n is the size of S and m is the size of T
make to pointers p1=0 and p2=0
make another array C[]={0,0,...} which c[i] counts the number
of occurrence of T[i] in S[p1],S[p1+1]...S[p2]
n1=0 is the number of nonzero elements in C so each time n1==m means that
range p1..p2 can be an answer
first
@ anand I think u did'nt get the point
what if T=['n' , 'n', 'a']
then if u reverse u wont get any LCS but answer is "nan" . Plz try to get
the jist of the question.
On Mon, Jul 12, 2010 at 10:44 PM, Anand wrote:
> @amit: In this case, we can calculate the length of string S and T and
> revers
@amit: In this case, we can calculate the length of string S and T and
reverse the string whose length is smaller than the other. Then Take LCS of
it. To get the final answer.
On Mon, Jul 12, 2010 at 7:05 AM, Amit Jaspal wrote:
> @ above Consider S="anand" T={'d','n'.'a'}
>
> LCS is "na" but th
@ above Consider S="anand" T={'d','n'.'a'}
LCS is "na" but the Answer is "and" . Here the order of characters don't
matter as i have mentioned .
One way is you can take LCS with every possible permutation of T but that
would be exponential
On Mon, Jul 12, 2010 at 3:23 PM, ankur aggarwal wrote:
i think ques is not complete..
otherwise above ans is rite.. i suppose..
On Mon, Jul 12, 2010 at 10:00 AM, Anand wrote:
> you can use longest common subsequence algorithm to solve it.
>
> http://codepad.org/NDAeIpxR
>
>
> On Sun, Jul 11, 2010 at 9:32 AM, amit wrote:
>
>> Given a set T of charac
you can use longest common subsequence algorithm to solve it.
http://codepad.org/NDAeIpxR
On Sun, Jul 11, 2010 at 9:32 AM, amit wrote:
> Given a set T of characters and a string S , find the minimum window
> in S which will contain all the characters in T in complexity O(n) .
>
> Constraint :
Given a set T of characters and a string S , find the minimum window
in S which will contain all the characters in T in complexity O(n) .
Constraint : The characters may appear in any order
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To
