Secret Cipher

Problem Overview

A * doubles the string decoded so far, so it can only replace a second copy of the current prefix.

Intuition

A * doubles the string decoded so far, so it can only replace a second copy of the current prefix. That is possible exactly when a prefix has even length and consists of an even number of copies of its smallest period. KMP LPS finds that period in linear time. Walking right-to-left greedily takes every such star (covering the largest repeating prefixes first) and yields the shortest encoding.

Algorithm

1Build the LPS array: lps[i] is the longest proper prefix that is also a suffix of s[0..i].
2Walk i from n-1 down to 1. Let len = i+1.
3If len is even, period = len - lps[i], and lps[i]*2 >= len, len % period == 0, and (len/period) is even: append * and jump to the first half (i = len/2 - 1).
4Otherwise append s[i] and decrement i.
5Append s[0], reverse the builder, and return it.

Example Walkthrough

Input: s = "ababcababcd"

1. Prefix "ababcababc" (len 10) is two copies of "ababc", so replace the second half with *.
2. Prefix "abab" is two copies of "ab", so another *.
3. Remaining letters give ab*c*d, which decompresses back to the original.

Output: ab*c*d

Common Pitfalls

• Odd-length prefixes cannot split into two equal halves, so they never get a star at that index.
• lps[i]*2 >= len is not enough - the smallest period must also divide len with an even copy count.
• Process from the right so nested stars (as in z*z*z for zzzzzzz) stay shortest.
• * is cheaper than writing the second copy of letters, so take every valid star.

Secret Cipher.java

Java

// Approach: KMP LPS. A prefix of even length can be written as two identical
// halves (so the second half becomes '*') iff its smallest period divides the
// length and the number of period copies is even. Walk right-to-left and
// greedily take every such star, then reverse.
// Complexity: O(n) time and O(n) space.

class Solution {

    public String compress(String s) {
        int n = s.length();
        char[] a = s.toCharArray();
        int[] lps = buildLps(a);

        StringBuilder out = new StringBuilder(n);
        int i = n - 1;
        while (i > 0) {
            int len = i + 1;
            if ((len & 1) == 0 && canStar(lps[i], len)) {
                out.append('*');
                i = (len >> 1) - 1;
            } else {
                out.append(a[i]);
                i--;
            }
        }
        out.append(a[0]);
        return out.reverse().toString();
    }

    private boolean canStar(int suffix, int len) {
        if (suffix * 2 < len) {
            return false;
        }
        int period = len - suffix;
        return len % period == 0 && ((len / period) & 1) == 0;
    }

    private int[] buildLps(char[] a) {
        int n = a.length;
        int[] lps = new int[n];
        int len = 0;
        for (int i = 1; i < n; ) {
            if (a[i] == a[len]) {
                lps[i++] = ++len;
            } else if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }
}

Was this solution helpful?