A string originalText is encoded using a slanted transposition cipher to a string encodedText with the help of a matrix having a fixed number of rows rows.
originalText is placed first in a top-left to bottom-right manner.
The blue cells are filled first, followed by the red cells, then the yellow cells, and so on, until we reach the end of originalText. The arrow indicates the order in which the cells are filled. All empty cells are filled with ' '. The number of columns is chosen such that the rightmost column will not be empty after filling in originalText.
encodedText is then formed by appending all characters of the matrix in a row-wise fashion.
The characters in the blue cells are appended first to encodedText, then the red cells, and so on, and finally the yellow cells. The arrow indicates the order in which the cells are accessed.
For example, if originalText = "cipher" and rows = 3, then we encode it in the following manner:
The blue arrows depict how originalText is placed in the matrix, and the red arrows denote the order in which encodedText is formed. In the above example, encodedText = "ch ie pr".
Given the encoded string encodedText and number of rows rows, return the original string originalText.
Note: originalText does not have any trailing spaces ' '. The test cases are generated such that there is only one possible originalText.
Example 1:
Input: encodedText = "ch ie pr", rows = 3 Output: "cipher" Explanation: This is the same example described in the problem description.
Example 2:
Input: encodedText = "iveo eed l te olc", rows = 4 Output: "i love leetcode" Explanation: The figure above denotes the matrix that was used to encode originalText. The blue arrows show how we can find originalText from encodedText.
Example 3:
Input: encodedText = "coding", rows = 1 Output: "coding" Explanation: Since there is only 1 row, both originalText and encodedText are the same.
Constraints:
0 <= encodedText.length <= 106encodedText consists of lowercase English letters and ' ' only.encodedText is a valid encoding of some originalText that does not have trailing spaces.1 <= rows <= 1000originalText.Problem Overview: The encoded string represents a message written into a matrix with a fixed number of rows, then read diagonally from the top-left toward the bottom-right. Given the encoded text and the number of rows, you need to reconstruct the original message and remove trailing spaces.
Approach 1: Using Matrix Reconstruction (O(n) time, O(n) space)
Compute the number of columns using cols = encodedText.length / rows. Rebuild the matrix by simulating the diagonal traversal used during encoding. Start from each column in the first row, move diagonally with (r + 1, c + 1), and place characters from encodedText into the matrix in that order. Once the matrix is reconstructed, iterate row by row to build the original string. Finally, remove trailing spaces because padding was added during encoding.
This approach mirrors the encoding process exactly, which makes the logic easy to reason about during debugging. The algorithm touches each character once, resulting in O(n) time complexity and O(n) auxiliary space for the matrix.
Approach 2: Simplified Character Reorganization (O(n) time, O(1) extra space)
You can skip building the matrix entirely. Since the encoded text corresponds to a matrix filled row-wise, the character at matrix position (r, c) exists at index r * cols + c in the encoded string. Iterate through each starting column in the first row and simulate the diagonal traversal. For every step, compute the index directly using encodedText[r * cols + (startCol + r)]. Append characters while startCol + r < cols.
This method reconstructs the plaintext in the same order as the diagonal read but avoids storing the full matrix. It uses simple index arithmetic and sequential iteration, which keeps the runtime O(n) and reduces extra memory usage to O(1) beyond the output buffer.
The problem is essentially a string traversal with a structured access pattern. Treating the encoded text as a virtual matrix and simulating the traversal is the key insight. The logic is also a classic example of simulation where you reproduce the exact steps used during encoding.
Recommended for interviews: The simplified character reorganization approach is typically preferred. It demonstrates that you understand how to map 2D matrix coordinates to a 1D string index and optimize space usage. Rebuilding the matrix first is still a good starting point because it clarifies the traversal pattern before moving to the constant-space solution.
This approach involves reconstructing the matrix from the encoded text and reading back to derive the original text. First, calculate the number of columns needed. Then fill in the columns row-wise using the encoded text. Finally, read the matrix diagonally from top-left to bottom-right to get the original text.
This C solution reconstructs the original text by determining columns from length div rows. It iterates over columns, reading diagonally into the resultant string.
Time Complexity: O(n), where n is the length of encodedText. Space Complexity: O(n) for storing the result.
This approach focuses on reducing unnecessary overhead by reorganizing characters directly from the encoded text. It navigates through the expected row and column positions, iterating and appending directly into a resultant string.
This simplified C approach reorganizes characters by column with diagonal offsets, while directly reducing overhead.
Time Complexity: O(n). Space Complexity: O(n).
First, we calculate the number of columns in the matrix cols = len(encodedText) / rows. Then, following the rules described in the problem, we start traversing the matrix from the top left corner, adding characters to the answer.
Finally, we return the answer, making sure to remove any trailing spaces.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string encodedText.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Using Matrix Reconstruction | Time Complexity: O(n), where n is the length of encodedText. Space Complexity: O(n) for storing the result. |
| Simplified Character Reorganization | Time Complexity: O(n). Space Complexity: O(n). |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Matrix Reconstruction | O(n) | O(n) | When clarity matters or when visualizing the matrix traversal during debugging |
| Simplified Character Reorganization | O(n) | O(1) | Preferred for interviews and optimized implementations with minimal memory |
2075. Decode the Slanted Ciphertext (Leetcode Medium) • Programming Live with Larry • 656 views views
Watch 2 more video solutions →Practice Decode the Slanted Ciphertext with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor