Skip to main content
Talentd

Decode the Slanted Ciphertext - Solution & Explanation

MediumStringSimulation15 min readAsked at: Amazon, Google, Grammarly
Practice this problem

Problem Statement

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 <= 106
  • encodedText consists of lowercase English letters and ' ' only.
  • encodedText is a valid encoding of some originalText that does not have trailing spaces.
  • 1 <= rows <= 1000
  • The testcases are generated such that there is only one possible originalText.

Approach Overview

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.

Approach 1: Using Matrix Reconstruction

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of encodedText. Space Complexity: O(n) for storing the result.

Try this approach in the editor →

Approach 2: Simplified Character Reorganization

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n). Space Complexity: O(n).

Try this approach in the editor →

Approach 3: Simulation

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Matrix ReconstructionO(n)O(n)When clarity matters or when visualizing the matrix traversal during debugging
Simplified Character ReorganizationO(n)O(1)Preferred for interviews and optimized implementations with minimal memory

Video Solution

Decode the Slanted Ciphertext | Detailed Intuition | 2 Approaches | Leetcode 2075 | codestorywithMIK • codestorywithMIK • 6,316 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Decode the Slanted Ciphertext easy or hard?
Decode the Slanted Ciphertext is considered a Medium-level problem on LeetCode. The main challenge is recognizing the diagonal traversal pattern and converting between 2D matrix coordinates and the 1D string index.
Decode the Slanted Ciphertext Python/Java solution
In Python or Java, compute cols = encodedText.length() / rows and simulate diagonal traversal from each column. Access characters using index mapping r * cols + (startCol + r) and append them to a result builder. After traversal, trim trailing spaces before returning the decoded message.
How to solve Decode the Slanted Ciphertext in O(n)?
First compute the number of columns as cols = encodedText.length / rows. Iterate over each starting column in the first row and simulate the diagonal movement (r + 1, c + 1). Use index mapping r * cols + (startCol + r) to fetch characters directly from the encoded string and append them to the result, then trim trailing spaces.
What is the best approach for Decode the Slanted Ciphertext?
The best approach uses direct index computation without explicitly building the matrix. Treat the encoded string as a virtual rows × cols grid and simulate the diagonal traversal using index math like r * cols + (startCol + r). This runs in O(n) time and O(1) extra space while keeping the implementation simple.
Is Decode the Slanted Ciphertext asked at Google/Amazon/Meta?
Problems involving matrix traversal, diagonal simulation, and string reconstruction appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying skills—matrix indexing and simulation—are commonly tested.
What data structure is used in Decode the Slanted Ciphertext?
The problem primarily uses string manipulation and a conceptual 2D matrix. Some solutions explicitly construct a matrix, while optimized solutions treat the string as a virtual matrix using index arithmetic. No complex data structures are required beyond arrays or strings.
What is the time complexity of Decode the Slanted Ciphertext?
The optimal solution runs in O(n) time where n is the length of encodedText. Each character is processed at most once during the diagonal traversal. Space complexity can be O(n) if a matrix is built, or O(1) extra space if you compute indices directly.

Ready to solve this problem?

Practice Decode the Slanted Ciphertext with our built-in code editor and test cases.

Practice on FleetCode
Previous

Diagonal Traverse