The guarantee is going to help us a lot here, and the guarantee is that it is always possible to make a palindrome by removing only one character. Obviously the most obvious approach is to take out every single character and check for palindrome but that gives us around (10^6)^2 complexity which will not fit in 1 second time limit for sure. Instead we can try a little trickier method, it is guaranteed that we are sure going to be able to form a palindrome, so if initially the first character is not equal to the last character then we can conclude that either we have to remove the first character in order to form a palindrome or the last. If they are equal then we need to check the second character to be equal to the pre-last character and if it is not then the character which must be removed is either the second one or the pre last one , and so on.
No comments:
Post a Comment