Introduction

The Secret Cipher problem asks us to find the lexicographically smallest encrypted string that can be decoded back into the given original string.

The special character * is used to represent a repeated prefix.

For example:

Original:
ababcababcd

Encrypted:
ab*c*d

When the decoding process encounters *, the characters before * are appended again. Therefore:

ab*c*d

can be decoded as:

ab → abc → ababc → ababcababcd

The challenge is to find the smallest possible encrypted representation efficiently for a string of length up to 100000.

Problem Understanding

Suppose we have:

s = "abab"

The string contains two identical halves:

ab | ab

Therefore, it can be represented as:

ab*

because * repeats the characters before it.

Similarly:

zzzzzz

contains repeated portions and can be compressed.

The goal is not simply to remove every possible repeated substring. We need to find the lexicographically smallest valid encrypted string.

Important Observation

Consider:

abab

The first half is:

ab

The second half is:

ab

Since both are equal:

abab = ab + ab

we can replace the second copy with:

ab*

This means we need a fast way to determine whether a string has a repeated prefix.

This is where the KMP algorithm becomes useful.

KMP Prefix Function / LPS

KMP stands for Knuth-Morris-Pratt.

One important part of KMP is the LPS array.

LPS means:

Longest Proper Prefix which is also a Suffix.

For:

s = "abab"

the LPS array is:

0 0 1 2

At the last character:

abab
^^
||
ab

The prefix "ab" is also a suffix "ab".

Therefore:

lps[3] = 2

Why LPS Helps Here

Suppose the current substring has length len.

If its longest prefix/suffix overlap is large enough, we can determine whether the string is made from repeated sections.

The basic relationship is:

period = len - lps[len - 1]

For example:

s = "abab"

len = 4
lps = 2

period = 4 - 2
       = 2

So the repeating unit is:

"ab"

and:

"abab"

is:

"ab" + "ab"

Therefore it can be compressed.

Java Implementation

class Solution {
    public String compress(String s) {
        int n = s.length();

        // Build KMP LPS array
        int[] lps = new int[n];

        for (int i = 1; i < n; i++) {
            int j = lps[i - 1];

            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = lps[j - 1];
            }

            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }

            lps[i] = j;
        }

        StringBuilder ans = new StringBuilder();

        int i = n - 1;

        while (i >= 0) {

            // Current length
            int len = i + 1;

            // A repeated-half compression is possible
            // only when length is even.
            if (len % 2 == 0) {

                int border = lps[i];

                // Minimum repeating period
                int period = len - border;

                if (border >= len / 2 &&
                    len % (2 * period) == 0) {

                    ans.append('*');

                    // Move to the first half
                    i = len / 2 - 1;

                    continue;
                }
            }

            ans.append(s.charAt(i));
            i--;
        }

        return ans.reverse().toString();
    }
}

Step 1 – Calculate the LPS Array

The first part of the code is:

int[] lps = new int[n];

for (int i = 1; i < n; i++) {
    int j = lps[i - 1];

    while (j > 0 && s.charAt(i) != s.charAt(j)) {
        j = lps[j - 1];
    }

    if (s.charAt(i) == s.charAt(j)) {
        j++;
    }

    lps[i] = j;
}

This is the standard KMP prefix-function construction.

For:

abab

we get:

Index:  0 1 2 3
String: a b a b
LPS:    0 0 1 2

The last value 2 tells us that "ab" is both a prefix and suffix.

Step 2 – Start From the End

After constructing the LPS array:

int i = n - 1;

we process the string from right to left.

Why?

Because we want to decide whether the current prefix can be replaced by *.

We maintain:

StringBuilder ans = new StringBuilder();

The answer is initially built backwards.

Step 3 – Check Whether the Current Length Is Even

int len = i + 1;

if (len % 2 == 0) {

A repeated-half compression requires:

first half == second half

For example:

abab

has:

ab | ab

So its length is even.

But:

abc

cannot be divided into two equal-length halves.

Therefore, we only try the compression when:

len % 2 == 0

Step 4 – Calculate the Border

int border = lps[i];

The border represents the longest prefix that is also a suffix.

Then:

int period = len - border;

gives the minimum repeating period.

For:

abab

we have:

len = 4
border = 2

period = 4 - 2
       = 2

So:

abab

has repeating unit:

ab

Step 5 – Verify Repetition

The important condition is:

if (border >= len / 2 &&
    len % (2 * period) == 0)

The first condition:

border >= len / 2

ensures that enough of the string overlaps with its prefix.

The second condition:

len % (2 * period) == 0

ensures that the entire current string can be represented by repeated copies of the same unit.

For:

abab

we have:

border = 2
len / 2 = 2

so:

2 >= 2

is true.

And:

4 % (2 × 2) = 0

is also true.

Therefore:

abab

can be compressed.

Step 6 – Add *

When compression is possible:

ans.append('*');

Instead of keeping the repeated second half, we store:

*

For example:

abab

becomes:

ab*

Then we only need to process the first half:

i = len / 2 - 1;

For:

len = 4

we get:

i = 4 / 2 - 1
  = 1

So processing continues with:

ab

Step 7 – Otherwise Keep the Character

If compression is not possible:

ans.append(s.charAt(i));
i--;

The current character is added normally.

For example:

abc

cannot be compressed, so its characters are retained.

Step 8 – Reverse the Answer

Because we process from right to left, the answer is initially backwards.

Therefore:

return ans.reverse().toString();

returns the final encrypted string in the correct order.

Example 1

Consider:

s = "ababcababcd"

The useful repeated structure is:

ababcababc

which can be represented as:

ababc*

Then the remaining structure can be compressed further.

The final result is:

ab*c*d

So:

Input:
ababcababcd

Output:
ab*c*d

Example 2

Consider:

s = "zzzzzzz"

There are many possible ways to represent repeated characters.

The lexicographically smaller compressed representation is:

z*z*z

The important point is that we should not simply choose the representation with the most * characters. We need the lexicographically smallest valid result.

Why Not Use Recursion?

A straightforward recursive solution might repeatedly try:

prefix + "*"

and recursively solve the remaining part.

However, with:

n = 100000

deep recursion can cause:

StackOverflowError

or excessive memory usage.

The iterative approach avoids this problem:

while (i >= 0) {
    ...
    i--;
}

So the algorithm is safe for large input sizes.

Complexity Analysis

Time Complexity

Building the LPS array takes:

O(n)

The second traversal also takes:

O(n)

Therefore:

Overall = O(n)

Space Complexity

The LPS array requires:

O(n)

and the answer requires:

O(n)

Therefore:

Auxiliary Space = O(n)

Key Takeaways

The main concepts used in this problem are:

  1. KMP prefix function

  2. LPS array

  3. Finding repeated prefixes

  4. Iterative processing from right to left

  5. StringBuilder for efficient string construction

  6. Avoiding recursion for large input

The most important KMP formula is:

period = len - lps[i];

and the repeated-structure check is based on whether the current prefix can be divided into valid repeated sections.

Final complexity

Time  : O(n)
Space : O(n)

This makes the approach suitable for:

1 ≤ |s| ≤ 100000