EASY SUBSEQUENCE SELECTION
The problem’s three conditions are as follows :
·
Subsequence A and Subsequence B
should be selected from given String S such that A=B .Since A = B ,its obvious
their length is equal and let it be equal to K.
·
When selecting indices from S to construct
subsequence A ,then from S we take indices a1,a2,a3…aK ,such that subsequence A
is Sa1+Sa2+Sa3+….SaK where +
denotes concatenation.
Similarly when selecting indices from
S to construct subsequence B ,then from S we take indices b1,b2,b3…bK ,such
that subsequence B is Sb1+Sb2+Sb3+….SbK
where + denotes concatenation.
·
In this third bullet point ,common
indices ‘M’ denotes the number of elements in the intersection of {a1,a2,a3,…aK}
and {b1,b2,b3…bK}
This condition requires M+1<= K
which can be inferred as M should be strictly less than K.
Now Our aim is to find the maximum value of K.
Considering Edge Case
Suppose if we are unable to find subsequences such
that M+1<=K then K value would not be valid .
Let’s see how is it possible
Minimum Value of M can be 0
Hence For Valid value of M, 0+1<=K should hold i.e
K>=1.So valid values of K are only from 1 to N.
Let’s see when validity of K fails. Suppose we have a
string consisting of only different lowercase alphabets. Then it’s very obvious
that we would not be able to generate any value of K.(Why? Lets See)
Because let’s suppose subsequence A takes first character as ith
character of string , then to parallelly generate a subsequence B we need
a position j in S such that S[i] = S[j] and
CASE 1:
i not equal to j
This
means we need position j such that S[j] = S[i] but we know we have only different
characters in S so this case fails here.
CASE 2: i is equal to j
This looks
fine but will eventually fail because if we increase K from 1 by using this
case then condition M+1<=K will not reach because at each step M will be
equal to K.
Hence for string S which only has different lowercase
alphabets then K will not exist and simply output 0 as answer.
Cases Apart from Edge Case
Let i be used for creating sub-sequences A and j be used
for creating sub-sequence B ,then :
Suppose we have initially selected indexes such that I
and j are kept equal at each selection step (we are parallelly creating A and B),hence
for this step M value is equal to K
value where M is intersection of indexes selected for constructing A and B and K is length of the subsequence A (or B).
We know M= K so we need to make M as strictly less
than K (for validity of answer).Hence suppose we need to select i and j such
that i is not equal to j but S[i] = S[j] .Let this i and j be equal to i’ and j’
.
So length K = min(i’,j’) because all indexes before min(i’,j’)
are taken into A and B both and then i’ is taken for A and j’ is taken from B(which
makes M!=K).
As we do this M=K becomes M<K because now M = K-1.This step is the actual logic building
part because we can see now that now any (i,j) selection further to build
sub-sequences A and B will never be able to make M equal to K .Hence we now select all the indexes from max(i’,j’)+1 to N so
that we reach maximum possible K.
So optimal answer K = min(i',j')+(N-max(i',j')) where I’
and j’ is assumed to be such that I’ != j’ and S[i’] = S[j’]
K = N-(max(i',j')-min(i',j')).
Now we need to simply find this i` and j` such that S[I’]
= S[j’] and i!=j and 1<=i,j<=N and
(max(i',j')-min(i',j')) should be minimum.
This can be easily done in two loops from 1 to N and
even in one loop by observing the equation .
Hope it helps .
For any query post comments.
