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:

Code
Original:
ababcababcd

Encrypted:
ab*c*d

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

Code
ab*c*d

can be decoded as:

Code
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:

Code
s = "abab"

The string contains two identical halves:

Code
ab | ab

Therefore, it can be represented as:

Code
ab*

because * repeats the characters before it.

Similarly:

Code
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:

Code
abab

The first half is:

Code
ab

The second half is:

Code
ab

Since both are equal:

Code
abab = ab + ab

we can replace the second copy with:

Code
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:

Code
s = "abab"

the LPS array is:

Code
0 0 1 2

At the last character:

Code
abab
^^
||
ab

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

Therefore:

Code
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:

Code
period = len - lps[len - 1]

For example:

Code
s = "abab"

len = 4
lps = 2

period = 4 - 2
       = 2

So the repeating unit is:

Code
"ab"

and:

Code
"abab"

is:

Code
"ab" + "ab"

Therefore it can be compressed.

Java Implementation

Java
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:

Java
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:

Code
abab

we get:

Code
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:

Java
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:

Java
StringBuilder ans = new StringBuilder();

The answer is initially built backwards.

Step 3 – Check Whether the Current Length Is Even

Java
int len = i + 1;

if (len % 2 == 0) {

A repeated-half compression requires:

Code
first half == second half

For example:

Code
abab

has:

Code
ab | ab

So its length is even.

But:

Code
abc

cannot be divided into two equal-length halves.

Therefore, we only try the compression when:

Java
len % 2 == 0

Step 4 – Calculate the Border

Java
int border = lps[i];

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

Then:

Java
int period = len - border;

gives the minimum repeating period.

For:

Code
abab

we have:

Code
len = 4
border = 2

period = 4 - 2
       = 2

So:

Code
abab

has repeating unit:

Code
ab

Step 5 – Verify Repetition

The important condition is:

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

The first condition:

Java
border >= len / 2

ensures that enough of the string overlaps with its prefix.

The second condition:

Java
len % (2 * period) == 0

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

For:

Code
abab

we have:

Code
border = 2
len / 2 = 2

so:

Code
2 >= 2

is true.

And:

Code
4 % (2 × 2) = 0

is also true.

Therefore:

Code
abab

can be compressed.

Step 6 – Add *

When compression is possible:

Java
ans.append('*');

Instead of keeping the repeated second half, we store:

Code
*

For example:

Code
abab

becomes:

Code
ab*

Then we only need to process the first half:

Java
i = len / 2 - 1;

For:

Code
len = 4

we get:

Code
i = 4 / 2 - 1
  = 1

So processing continues with:

Code
ab

Step 7 – Otherwise Keep the Character

If compression is not possible:

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

The current character is added normally.

For example:

Code
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:

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

returns the final encrypted string in the correct order.

Example 1

Consider:

Code
s = "ababcababcd"

The useful repeated structure is:

Code
ababcababc

which can be represented as:

Code
ababc*

Then the remaining structure can be compressed further.

The final result is:

Code
ab*c*d

So:

Code
Input:
ababcababcd

Output:
ab*c*d

Example 2

Consider:

Code
s = "zzzzzzz"

There are many possible ways to represent repeated characters.

The lexicographically smaller compressed representation is:

Code
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:

Code
prefix + "*"

and recursively solve the remaining part.

However, with:

Code
n = 100000

deep recursion can cause:

Code
StackOverflowError

or excessive memory usage.

The iterative approach avoids this problem:

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

So the algorithm is safe for large input sizes.

Complexity Analysis

Time Complexity

Building the LPS array takes:

Code
O(n)

The second traversal also takes:

Code
O(n)

Therefore:

Code
Overall = O(n)

Space Complexity

The LPS array requires:

Code
O(n)

and the answer requires:

Code
O(n)

Therefore:

Code
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:

Java
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

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

This makes the approach suitable for:

Code
1 ≤ |s| ≤ 100000