Longest Weird SubsequenceProblem code: LWS |
All submissions for this problem are available.
Finding the longest increasing subsequence is an old and well-known problem now. Here you will have to do something similar. You need to find the longest weird subsequence (LWS) of the given string. The subsequence is called weird if it can be split into two disjoint subsequences, one of which is non-decreasing and the other one is non-increasing.
Just for clarity, by subsequence of the given string S we mean any string that can be obtained from S by erasing from it zero or more characters. So empty string is a subsequence of any string and any string is a subsequence of itself. Further, note that we consider only strings composed of lowercase Latin letters and these letters compared by their ASCII codes. So, for example, 'a' is smaller than 'b' and 'p' is larger than 'h'.
Now let's consider some example. Let S="aabcazcczba". Then "abczz" is its some non-decreasing subsequene, "zccb" is its some non-increasing subsequence and "aabczcczba" is its some weird subsequence since it can be split into non-decreasing subsequence "aabzz" and non-increasing subsequence "cccba": "AABcZccZba" (first subsequence is shown by capital letters just for calrity).
Input
The first line contains a single positive integer T, the number of test cases. T test cases follow. The only line of each test case contains a non-empty string S composed of lowercase Latin letters.
Output
For every test case, output the length of the LWS of the given string.
Constraints
1 ≤ T ≤ 10 1 ≤ length of S ≤ 2000
Example
Input 3 abc cbazyzabc ddaabbaacc Output 3 6 10
Explanation
First case: The string itself is LWS since it can be split into non-decreasing subsequence "abc" and non-increasing empty subsequence.
Second case: One of the possible LWS is "cbaabc" since it can be split as "cbaABC". Here we indicate by capital letters non-decreasing subsequence and by lowercase letters non-increasing one. Other possible LWS's are "cbaZZa", "AzyaBC".
Third case: Here the desired splitting is "ddAABBaaCC".
| Author: | vamsi_kavala |
| Tester: | anton_lunyov |
| Editorial | http://discuss.codechef.com/problems/LWS |
| Date Added: | 29-07-2011 |
| Time Limit: | 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
Can an empty string be
@shadow: Yes, thus the answer
in 3rd case ddAABBaaCC ddBBaa
@ashmish2 : They need to be
@admin LWS for second case
@ashmish2: Please do not
some other test cases please
@admin One tricky test case,
will O(n*n) pass ??
@manoharsingh23: Please do
@vamsi_adm : i regret if i
@manoharsingh23: Yeah, you
@admin Hey! my code is
an somebody tell meaning of
Query: Anybody noticed that
@mpossible: I guess disjoint
@vamsi_adm : can there be
@nikku: No.
over and over i'm getting
i m getting "wrong
@vector9x and palak_agarwal:
So, contest ends. can someone