can anyone please explain the logic of double string question ?? plz
Goto this link and post your question:
Double String means a string in which the First Half of the String is Exactly Equal to the Second Half. Like “abababab” -> First Half = “abab” -> Second Half = “abab”. Both are same therefore this String is a double String.
Double String unlike Palindromes can have only EVEN Length. Like “abaab” is not a Double String even though strings around the middle character are same.
Now in the Problem you are given a Palindrome and you have to tell the Maximum length of Double String which can be created using this. You can Remove some Characters and Also can Change the Order of Characters.
If you are given a Palindrome of Even Length------
“abba” - In this String you can Interchange the last two characters so that the String becomes - “abab” which is a Double String. So the Nutshell is that you can generate Double String from a Palindrome String of the same Length just by Reversing the Order of Second Half of the String.
If length of Palindrom is n(even) then length of Double String = n.
If you are given a Palindrome of Odd Length-------
“ababa” - In this String you can remove the Middle Character ‘a’ and the String becomes - “abba”.
Now you can easily make a Double String out of it. Note that you cannot have Double String of Odd length.
If Length of Palindrom String is n(Odd) then length of Double String = n-1.
Instead …If I understand the question correctly…you can remove middle character in case of the string being of odd length.
Now take the string and divide it in two halves.
Now take the character count in each half.
Take the minimum count of the character by comparing count in each halves for each character.
Add all those minimum and you will have the result.
for 1st half ababbc
count of a=2
count of b=3
count of c=1
for 2nd half ababaa
count of a=4
count of b=2
count of c=0
min count of a=2
min count of b=2
min count of c=0
got it…!!! thanx a lot