This article describes the question from Day 11 of the 30 Days of Code competition hosted by Geeks for Geeks.

Question

Geek wants to send an encrypted message in the form of a string S to his friend Keeg along with instructions on how to decipher the message. To decipher the message, his friend needs to iterate over the message string from left to right, if he finds a '*', he must remove and add all the letters read so far to the string. He must keep on doing this till he gets rid of all the '*'.

Can you help Geek encrypt his message string S?

Note: If the string can be encrypted in multiple ways, find the smallest encrypted string.

Example 1:

Input: S = "ababcababcd"
Output: ab*c*d
Explanation: We can encrypt the string in the following way: "ababcababcd" --> "abacb*d" -> "ab*c*d"

Example 2:

Input: S = "zzzzzzz"
Output: z*z*z
Explanation: The string can be encrypted in 2 ways: "z*z*z" and "z**zzz". Out of the two "z*z*z" is smaller in length

Your task:

You don't need to read input or print anything. Complete the function secretCipher() which takes the message string S as an input parameter and returns the shortest possible encrypted string.

Expected Time Complexity: O(N) Expected Auxillary Space: O(N)

Constraints: 1 <= |S| <= 10^5

Solution

class Solution:
    def compress(self, s):
        n = len(s)
        v = [0]*n
        r = ''
        for i in range(1,n):
            j = v[i-1]
            while j > 0 and s[i] != s[j]:
                j = v[j-1]
            if s[i] == s[j]:
                j += 1
            v[i] = j
        i = n - 1
        while i >= 0:
            if i % 2:
                if v[i] >= (i+1)/2 and (i+1)%(2*(i+1-v[i])) == 0:
                    r += ('*')
                    i = i // 2 + 1
                else:
                    r += s[i]
            else:
                r += s[i]
            i -= 1
        return r[::-1]

The first loop in this code generates the Longest Suffix Prefix (LSP) for the input string. In our case, since we are looking for repetition the suffix and prefix are the same. We use this array v to work out the compression of the string later.

The while loop iterates over the LSP backwards. We start from the final index position n - 1. If i is an odd number, we may have an equal suffix and prefix. So we check for this condition. If so, we append an asterisk '*', and half the i pointer then add 1. Otherwise, we can just append the current character to our answer s.

If it is an even number, it is not possible to have a matching suffix and prefix, since they would be of different lengths. So we just append the current character to s. Each iteration of the loop we decrement our counter i by one regardless. Lastly, we return the compressed string r. Since we constructed it from end to start, we must reverse the string r, then return it.