[Community Puzzle] Longest Palindrome

Puzzles
#1

Hi guys,

I’m trying to do this community puzzle. I started checking all possibilities vs the reversed one, in length descending order, so i can stop when one is found. But my program timeout for 5000 chars.

Any ideas on optimizing this ?

Thanks

#2

Hi
Did you try to find a palindrome from the middle of the sentence or from another position in the sentence? In O(n)…

#3

I’m starting at the first char (position 0)

#4

Try to check for characters, that are only one time included, because you can skip this ones.
in LABA, the L is a single character so you could skip it, if you don’t find any solution at all like in ABCD, you can output every single digit as single digit palindrom

Your Essigautomat

#5

I’m blocked with the last case: cyclic palindrom. It’s so frustrating :slight_smile:

#6

Anyone knows what the validator 05 - DNA long (5000 chars) is about?
I passed all tests and validator except this one…

#7

Yes, 5000 characters.
And 2 palindromes with length 13.

#8

Using C# and timing out on 5000+ characters. I also tried implementing Manacher’s algorithm found here: https://en.wikipedia.org/wiki/Longest_palindromic_substring
And I can make it output one of the longest, but not several palindromes of same length.
Is the C# timeout too strict? Is a O(n) or a max O(n^2) solution really needed? I think my original solution is O(n^3), which times out.

#9

4 posts were merged into an existing topic: Cyclic palindrome

#10

can anyone help me?
im trying to solve the puzzle with palindrome and i am blocked at a last case ‘cyclic palindrome’
who can tell me what the “cyclic palindrome” is?

#11

I checked the validator, you need to find a palindrome in which there is a two letters cycle. For example: O GO GO (GO is the cycle).

#12

Hello,

I have issues to solve in Swift at 100% the puzzle Longest palindrome (Hard) by Maurice_Moss.

My code have issues starting at the 5th test, the timeout is too short and got an error. I have implemented the same algorithm from a working one in Java, and failed in Swift, can you help me. Is it a complexity issue ? I’m stuck at 50%.

I have constraints in Swift if I want to use Substrings,… I cannot use directly Int, I must to use String.Index (main reason is due to the possibility to use extended UTF-16 characters like emojis,… that takes 2 or more index sizes for only one character like that).

There is the part I have put to do that, but timeout is too short to pass the test and validators:

extension String {
	// Similar to charAt in Java. Warning O(n) complexity.
	func charAt(_ idx: Int) -> Character {
		return self[self.index(self.startIndex, offsetBy: idx)]
	}

// Similar to substring in Java. Warning O(n) complexity.
func substring(start: Int, end: Int) -> String {
	let b = self.index(self.startIndex, offsetBy: start)
	let e = self.index(self.startIndex, offsetBy: end)

	return String(self[b..<e])
}

}

I cannot found any way to get a character at a specific index and substring with a reduced complexity.
Can you help me ?

Thanks for your answer.

[Community Puzzle] Longest Palindrome
#13

Store all chars of your string individually in an array.
The complexity of this operation will be O(n) but you’ll do this only once, and then you’ll have access to any char in O(1).
Alternatively, you can store the indexes of the chars instead of the chars themselves.

1 Like
#14

I have issues with that, first test says fatal error. I have found an other way, but not working well, I’m now stuck at 75%.
Passed test: 1, 2, 3, 4 and 7. Passed validators: 1, 2, 3, 4, 5, 6.
I think you can help me, I will send you my code in PM.

Thanks if you can help me.

#15

Finally succeeded. Now at 100%, 5 hard puzzles solved.

#16

i need some help all tests passed except 6, my program devide the string input and takes only 4095 first characters from it this issue i got in several puzzels , this time with python has someone the same issue ?