🔗 String Compression

"Apeach," who wants to become a data processing expert, is studying methods for compressing strings. She's recently been studying a simple lossless compression method for processing large amounts of data, which represents consecutive occurrences of the same value in a string using the count of the character and the repeated value, expressing it as a shorter string.

As a simple example, "aabbaccc" can be represented as "2a2ba3c" (when a character appears only once with no repetition, the 1 is omitted), but this method has the downside that the compression ratio is low when there are few repeated characters. For example, a string like "abcabcdede" isn't compressed at all. To address this drawback, "Apeach" is trying to find a way to split the string into units of 1 or more characters before compressing it, so it can be represented as a shorter string.

For example, in the case of "ababcdcdababcdcd", splitting the characters into units of 1 doesn't compress it at all, but splitting it into units of 2 lets it be represented as "2ab2cd2ab2cd". Alternatively, splitting it into units of 8 gives "2ababcdcd", which is the shortest possible representation in this case.

As another example, for "abcabcdede", splitting it into units of 2 gives "abcabc2de", but splitting it into units of 3 gives "2abcdede", making 3 the unit that yields the shortest compression. In this case, when splitting into units of 3, any leftover characters at the end are simply appended as-is.

Given a string s to compress as a parameter, complete the solution function that returns the length of the shortest string obtainable by splitting the string into units of 1 or more characters and compressing it as described above.

• The length of s is between 1 and 1,000, inclusive.
• s consists only of lowercase alphabet letters.

Example #1

Splitting the string into units of 1 character yields the shortest compression.

Example #2

Splitting the string into units of 8 characters yields the shortest compression.

Example #3

Splitting the string into units of 3 characters yields the shortest compression.

Example #4

Splitting the string into units of 2 characters gives "abcabcabcabc6de".

Splitting the string into units of 3 characters gives "4abcdededededede".

Splitting the string into units of 4 characters gives "abcabcabcabc3dede".

Splitting the string into units of 6 characters gives "2abcabc2dedede", and its length of 14 is the shortest.

Example #5

The string must be split starting strictly from the front, in fixed-length chunks.

Therefore, it's not possible to split the given string as x / ababcdcd / ababcdcd.

In this case, no matter how you split the string, it can't be compressed, so the shortest length is 17.

We need to implement a lossless string-compression algorithm.

1. Cut the string into chunks of length n starting from the front, generating the reference string to be compressed against.
2. Compare the contents of the string, and if it matches the reference chunk, compress it.
   1. If only one instance is compressed, there's no point in compressing, so the number is omitted and it's simply represented as abc.
   2. If two or more instances are compressed, it's represented as 2abc.
3. Once compression of the reference chunk is finished, repeat compression starting from the remaining string.

The key points are that the reference chunk must always be cut starting from the front of the string, and that n never exceeds s.length() / 2.

Looking at xababcdcdababcdcd in Input Example 5, you can clearly see this characteristic — the character x, which appears only once in the entire string, sits at the very front.

Because of this, compression is impossible no matter how you split it.

If x hadn't been at the front, a high compression ratio would have been achieved with n = 2.

Also, attempting to compress using a chunk length exceeding half the string's length is pointless.

In this section, we declare a compression method called compress. compress takes a string s and the chunk size num to compress by.

compress attempts compression by cutting the string s into chunks of size num.

1. Define the reference chunk to be compressed.
2. Attempt compression in chunks of length num.
   1. If it matches the reference chunk, increment the compression count.
   2. If it doesn't match the reference chunk, record what has been compressed so far and reset the compression count.
   3. If the reference chunk would extend past the length of s, record the remaining string.
3. Return the recorded contents.

JAVA
/**
 * String Compression class
 *
 * @author RWB
 * @since 2021.12.13 Mon 23:30:16
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param s: [String] string
	 *
	 * @return [int] answer
	 */
	public int solution(String s)
	{
		int answer = s.length();

		// Compressing beyond half the string's length is meaningless.
		for (int i = 1; i <= s.length() / 2; i++)
		{
			String a = compress(s, i);

			answer = Math.min(answer, a.length());
		}

		return answer;
	}

	/**
	 * Method that returns the compression result
	 * 
	 * @param s: [String] string
	 * @param num: [int] compression chunk size
	 *
	 * @return [String] compressed string
	 */
	private String compress(String s, int num)
	{
		int count = 1;

		String pattern = s.substring(0, num);

		StringBuilder builder = new StringBuilder();

		for (int i = num; i < s.length(); i += num)
		{
			// If the comparison index goes past the length of s
			if (i + num > s.length())
			{
				// Compression isn't possible here to begin with, so skip it

				builder.append(s.substring(i));
			}

			// Otherwise
			else
			{
				String target = s.substring(i, i + num);

				// If the string matches the pattern
				if (target.equals(pattern))
				{
					count++;
				}
				
				// If it doesn't match
				else
				{
					// If it can be compressed 2 or more times
					if (count > 1)
					{
						builder.append(count);

						count = 1;
					}
					
					builder.append(pattern);

					// Update the pattern
					pattern = target;
				}
			}
		}

		// If it can be compressed 2 or more times
		if (count > 1)
		{
			builder.append(count);
		}

		builder.append(pattern);

		return builder.toString();
	}
}