Connection Status:
Competition Arena > PalindromeEncoding

PalindromeEncoding

SRM 324 · 2006-10-25 · by AdrianKuegel

SRM 324 · 2006-10-25 · by AdrianKuegel · Dynamic Programming, Encryption/Compression, Recursion
Class Name: PalindromeEncoding
Return Type: int
Method Name: getLength
Arg Types: (string)
Problem Statement

Problem Statement

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

  1. 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.
  2. Remove the last half of the selected palindrome from s. For example, if the palindrome is "0110", remove the "10". Go to step 1.
  3. 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.

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • s will contain only the digits '0' and '1'.
Examples
0)
"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".

1)
"10000011110101101001000001100011110001100011001110"
Returns: 2
2)
"00000000000000000000000000000000000000000000000000"
Returns: 1
3)
"11111111111111111111111111111111111111111111111111"
Returns: 1
4)
"0"
Returns: 1

There is no palindrome of even length in this string, so nothing is changed.

Submissions are judged against all 120 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PalindromeEncoding with a public method int getLength(string s) · 120 test cases · 2 s / 256 MB per case

Submitting as anonymous