Decode the Slanted Ciphertext

Problem

We are given the encoded string encodedText and the number of rows rows.

During encoding, the original string is written diagonally into a matrix from top-left to bottom-right. After that, the matrix is read row by row to form encodedText.

Our job is to reverse that process and rebuild the original string.

One more detail matters a lot: the original string never has trailing spaces, so after decoding we must remove the extra spaces added during encoding.

Key Observation

If the encoded string has length n, then the matrix must have:

• rows rows
• cols = n / rows columns

Why?

Because the matrix was flattened row by row into encodedText, so encodedText already contains every cell of that matrix.

Once we know the matrix dimensions, we do not actually need to build the matrix separately.

We can directly access any matrix cell using:

index = row * cols + col

How Decoding Works

The original text was written along diagonals.

So to decode:

1. start from each column in the first row
2. move diagonally down-right
3. collect characters until we go out of bounds

That diagonal walk exactly reconstructs the original writing order.

For example, if we start from column c, then the visited cells are:

• (0, c)
• (1, c + 1)
• (2, c + 2)

and so on.

Approach

1. Handle the single-row case

If rows == 1, nothing is slanted at all, so the answer is simply encodedText.

2. Compute the number of columns

cols = encodedText.length() / rows

3. Traverse every diagonal

For every starting column c from 0 to cols - 1:

• set row = 0
• set col = c
• keep moving while row < rows and col < cols
• append encodedText[row * cols + col]

4. Remove trailing spaces

The matrix may contain filler spaces on the right side, so the decoded result can end with spaces that do not belong to the original string.

We trim only the trailing spaces and return the final answer.

Dry Run

Take:

encodedText = "ch   ie   pr", rows = 3

Here:

• n = 12
• cols = 12 / 3 = 4

Think of the encoded text as a 3 x 4 matrix:

c h _ _
_ i e _
_ _ p r

Now read diagonally:

• start at column 0: c -> i -> p
• start at column 1: h -> e -> r
• start at column 2: space
• start at column 3: space

That gives:

"cipher  "

After trimming trailing spaces:

"cipher"

Why This Works

The encoding process writes characters in diagonal order but stores them row by row.

So decoding is just the reverse viewpoint:

• treat encodedText as the matrix content
• walk the matrix in the same diagonals that were originally used to place characters

Because each diagonal is read in the same order it was written, the reconstructed string is correct.

Complexity Analysis

Time Complexity: O(n)

• every character in the matrix is visited at most once

Space Complexity: O(n)

• the result builder stores the decoded string

Common Mistakes

1. Forgetting to remove trailing spaces

Those spaces were only padding used to complete the matrix.

2. Building diagonals from every cell

We only need to start from the first row. Starting from every cell would duplicate work.

3. Miscomputing the index in the flattened matrix

The correct formula is:

row * cols + col

not row * rows + col.

Multi-language Solution

Use the tabs below to switch between Java, C++, JavaScript, TypeScript, C, C#, Go, and Rust implementations.

class Solution {
    public String decodeCiphertext(String encodedText, int rows) {
        if (rows == 1) {
            return encodedText;
        }

        int n = encodedText.length();
        int cols = n / rows;
        StringBuilder res = new StringBuilder(n);

        for (int c = 0; c < cols; c++) {
            int r = 0;
            int j = c;

            while (r < rows && j < cols) {
                res.append(encodedText.charAt(r * cols + j));
                r++;
                j++;
            }
        }

        int end = res.length() - 1;
        while (end >= 0 && res.charAt(end) == ' ') {
            end--;
        }

        return res.substring(0, end + 1);
    }
}