Problem Statement in English

You’re given a string encodedText that was encoded with a slanted transposition cipher. The encoding process can be described as follows:

  1. The original text is written in a matrix with rows rows and N columns (where N is the length of encodedText divided by rows).
  2. The characters are filled in the matrix in a slanted manner, starting from the top-left corner and moving diagonally down to the right. When the bottom of the matrix is reached, the filling continues from the top of the next column.
  3. The encoded text is then read from the matrix column by column, starting from the leftmost column.

Given the encoded text and the number of rows used in the encoding process, your task is to decode the text and return the original string. The decoded string should not contain any trailing spaces.

Approach

We basically need to iterate through the matrix in a diagonal manner and construct the original string.

We can do this by cleverly converting the 2D indices to 1D indices while traversing the given encoded string.

We will maintain two pointers, i and j, to keep track of our current position in the matrix. We will also maintain a variable col to keep track of the current column we started filling from.

Next we can append the characters to our result list as we traverse the matrix.

Finally, we will join the characters in the result list and remove any trailing spaces before returning the decoded string.

And we’re done!

Solution in Python


class Solution:
    def decodeCiphertext(self, encodedText: str, rows: int) -> str:
        if rows == 1:
            return encodedText
        
        L = len(encodedText)
        M = rows
        N = L // M

        i = j = col = 0
        res = []
        
        while j < N:
            res.append(encodedText[i * N + j])

            if i + 1 >= M or j + 1 >= N:
                i = 0
                j = col + 1
                col += 1
            else:
                i += 1
                j += 1

        return "".join(res).rstrip()

Complexity

  • Time: $O(M \times N)$
    Since we traverse the entire matrix once.

  • Space: $O(1)$
    Since we only use a few variables to keep track of the indices and the result.

And we are done.