By aditya1703, history, 11 months ago,

Given a string Str, rearrange Str such that the resultant string T maximizes min (LCS(Str, T) and LCS(Str, reverse(T))).

• +1

 » 11 months ago, # |   -9 looks like min (LCS(Str, T) and LCS(Str, reverse(T))) cannot exceed longest palindromic subsequence of Str, hence T=Str should work, i may be wrong tho
•  » » 11 months ago, # ^ |   0 Actually it can exceed that.Let $str = \text{aabb}$, $T = \text{abba}$. Now, $\min(\mathrm{LCS}(\text{aabb}, \text{abba}), \mathrm{LCS}(\text{aabb}, \text{abba})) = \min(3, 3) = 3$.If you choose $T = str$, you get $\min(\mathrm{LCS}(\text{aabb}, \text{aabb}), \mathrm{LCS}(\text{aabb}, \text{bbaa})) = \min(4, 2) = 2$.
•  » » » 11 months ago, # ^ |   0 yeah, i knew most probably my claim must be wronganyways, please tell how to solve the above problem
 » 11 months ago, # |   0 I think the answer is $\lfloor\frac{n + |P|}{2}\rfloor$, where $|P|$ is the maximum palindrome size.
•  » » 11 months ago, # ^ |   0 why?
•  » » 11 months ago, # ^ |   0 I will provide a construction as well as a proof of optimality. First, let's start with a proof of optimality. notice that $LCS(Str, reverse(T)) = LCS(reverse(Str), T)$. Now, let's say $s_1 = LCS(Str, T)$ and $s_2 = LCS(reverse(Str), T)$. Then, we must have that $|s_1| + |s_2| - |s_1 \cap s_2| \leq n = |T|$As $T$ must be an intertwining of the sub-sequences $s_1$ and $s_2$ with some positions that are common to both of them, and some positions that belong to neither of them. Here $s_1 \cap s_2$ denotes the positions in $T$ that are common to both $s_1$ and $s_2$. Now, notice that $s_1 \cap s_2 \leq |LCS(s_1, s_2)|$. Therefore, we must have that $|s_1| + |s_2| - |LCS(s_1, s_2)| \leq n$But $s_1$ is a sub-sequence of $Str$, and $s_2$ is a sub-sequence of $reverse(Str)$. Therefore, $|LCS(s_1, s_2)| \leq |LCS(Str, reverse(Str))| = |P|$which is the length of longest palindromic substring. Hence, $|s_1| + |s_2| - |P| \leq |s_1| + |s_2| - |LCS(s_1, s_2)| \leq n$Which implies that $min(|s_1|,|s_2|) \leq \frac{|s_1| + |s_2|}{2} \leq (N+|P|)/2$I will provide the construction in another comment.
•  » » 11 months ago, # ^ |   0 Consider the longest palindromic substring of $Str$, call it $P = \{ p_1, p_2, ..., p_n \}$. Then \we must have that $p_i = p_{n+1-i} \forall \ 1\leq i\leq n$. Now, remove this substring from $Str$, and assign the left-half substring to $s_1$ and reverse of the right-half substring to $s_2$. So, the the assignment will look like $a_1 \ P_1 \ a_2 \ P_2 ... \ P_k \ a_{k+1} \ b_{n-k+1} \ P_{k+1} \ b_{n-k} \ P_{k+2} \ ... \ P_n \ b_1$where $a$ denotes that this position belongs to the left-half substring and $b$ denotes that it belongs to the right half sub-string. Now, we're going to construct the string $T$ as follows $T = a_1 \ reverse(b_1) \ P_1 \ a_2 \ reverse(b_2) \ P_2 \cdots$Notice that for this sub-string, $LCS(T, Str) = \lfloor(\frac{n-|P|}{2})\rfloor + |P|$and $LCS( T, Reverse(Str)) = \lceil\frac{n-|P|}{2}\rceil + |P|$