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:
KMP prefix function
LPS array
Finding repeated prefixes
Iterative processing from right to left
StringBuilder for efficient string construction
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