PalindromeEncoding | Topcoder Archive

Problem Statement

The following algorithm can be used to encode a sequence of characters s:

Find any palindrome of even length in s. A palindrome is a string that reads the same forward and backward. If there are no palindromes of even length, go to step 3.
Remove the last half of the selected palindrome from s. For example, if the palindrome is "0110", remove the "10". Go to step 1.
Print the remaining sequence of characters.

Note that the resulting sequence is not necessarily unique since there may be multiple palindromes to choose from in step 1.

Given a String s containing only the digits '0' and '1', return the length of the shortest possible string that can result from applying the above algorithm to s.

Definition

Class:: PalindromeEncoding
Method:: getLength
Parameters:: String
Returns:: int
Method signature:: int getLength(String s)
(be sure your method is public)

Constraints

s will contain between 1 and 50 characters, inclusive.
s will contain only the digits '0' and '1'.

Examples

```
"0111001"
```
```
Returns: 2
```
First, take the last four digits and remove the "01" to get "01110". Then, select either of the "11"s and remove a "1" to get "0110". Finally, since the entire string is now a palindrome, you can remove the "10" to get "01".
```
"0"
```
```
Returns: 1
```
There is no palindrome of even length in this string, so nothing is changed.

"01010111100110101110000001011000101000010111000111"

Returns: 6

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.