Oh I think i wasn't thinking straight... I think the problem can be solved by simply removing 'i' letters from the string and check if that is a palendrome. where i would go from 1 to lenght.
But when i > 1...will i need to select all possible 2 length strings from the word and remove them one by one and check the remaining if it's a palendrom? That sounds like a pretty complex task... and what about i>2..i>3...what would you say the complexity of the solution be? On 3/30/07, Dhruva Sagar <[EMAIL PROTECTED]> wrote: > > Yes, i read the problem again. My interpretation was incorrect. > Generally one tends to interpret a problem in a way it's a bit easier to > understand :D. That happened with me on this occasion. > > It's a pretty complex problem from where i see it. and time limit:10 > seconds!!! Seems rather too less... > > Can you throw some more light on the logic how one should proceed solving > this problem? > > On 3/30/07, Muntasir Azam Khan < [EMAIL PROTECTED]> wrote: > > > > > > >Are you really sure that your assumption is correct? > > > > Yes, I'm sure. I solved this problem during the actual online contest at > > UVa. > > > > >I am not sure about the fact that you can take sub strings from the > > word by > > >removing characters from between them... > > >AAM is certainly not valid sub string for this case as far as my > > >understanding of the problem stands. > > > > Here's what the problem says, > > > > "From any non-palindromic string, you can always take away some letters, > > and > > get a palindromic subsequence." > > > > It does not mention the word 'substring' anywhere in the problem > > statement, > > but it does talk about subsequences. > > And it does not say anywhere that the letters we are taking away have to > > be > > from the end or the beginning. > > Think about the differenrence between substrings and subsequences. If > > you > > only check the substrings, > > you are bound to get a wrong answer. Your understanding of the word > > 'substring' is correct, > > but the question asks that we check all subsequences. > > > > Muntasir > > > > > > > > > > > > > -- > Thanks & Regards, > Dhruva Sagar. -- Thanks & Regards, Dhruva Sagar. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
