# Decode the Slanted Ciphertext
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/decode-the-slanted-ciphertext)
Canonical: https://scaleengineer.com/dsa/problems/decode-the-slanted-ciphertext
**Data structures:** String
**Companies:** [Grammarly](https://scaleengineer.com/companies/grammarly)
---
## Problem
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.

![](https://assets.glich.co/dsa/decode-the-slanted-ciphertext/image0.png) 

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.

![](https://assets.glich.co/dsa/decode-the-slanted-ciphertext/image1.png) 

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:

![](https://assets.glich.co/dsa/decode-the-slanted-ciphertext/image2.png) 

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:**

![](https://assets.glich.co/dsa/decode-the-slanted-ciphertext/image3.png) 

**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:**

![](https://assets.glich.co/dsa/decode-the-slanted-ciphertext/image4.png) 

**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`.

# Approaches
## Simulation using a 2D Matrix
This approach involves reconstructing the 2D matrix that was used for encoding. First, we determine the matrix dimensions from the length of `encodedText` and the given number of `rows`. Then, we fill this matrix with characters from `encodedText` in a row-wise manner. Finally, we read the matrix diagonally, as described in the encoding process, to retrieve the `originalText`. Any trailing spaces in the resulting string are removed.
**Time:** O(N), where N is the length of `encodedText`. Populating the matrix takes O(N) time. Traversing the matrix to build the result string also takes O(N) time as each cell is visited at most once. · **Space:** O(N), where N is the length of `encodedText`. This is because we allocate a `rows x cols` matrix, and `rows * cols = N`. The `StringBuilder` also requires up to O(N) space.
**Pros:** The logic is easy to follow as it directly models the physical grid.; Implementation is straightforward.
**Cons:** Requires extra space proportional to the size of the input string to store the 2D matrix, which can be significant for large inputs.
### Explanation
The most straightforward way to solve this problem is to simulate the process in reverse. We are given the row-wise flattened representation of a matrix (`encodedText`) and the number of rows.

1.  **Determine Matrix Dimensions**: The number of rows is given. The number of columns can be calculated since `encodedText.length() = rows * cols`. Thus, `cols = encodedText.length() / rows`. A special case is when `encodedText` is empty, in which case the original text is also empty.

2.  **Reconstruct the Matrix**: We create a 2D character array, say `grid`, of size `rows` by `cols`. We then populate this `grid` by iterating through `encodedText` from beginning to end, filling the `grid` row by row.

3.  **Decode by Diagonal Traversal**: The `originalText` was placed diagonally. To decode, we read the `grid` diagonally. The diagonals start at `(0, 0), (0, 1), (0, 2), ...`. We can iterate through each starting column `j` from `0` to `cols - 1`. For each `j`, we trace the diagonal path `(0, j), (1, j+1), (2, j+2), ...` and append the characters to a `StringBuilder`.

4.  **Handle Trailing Spaces**: The problem guarantees that the `originalText` does not have trailing spaces. Our diagonal traversal might pick up space characters that were used for padding. Therefore, the final step is to remove any trailing spaces from the string built by the `StringBuilder`.

```java
class Solution {
    public String decodeCiphertext(String encodedText, int rows) {
        int n = encodedText.length();
        if (n == 0) {
            return "";
        }
        int cols = n / rows;
        char[][] grid = new char[rows][cols];
        for (int i = 0; i < n; i++) {
            grid[i / cols][i % cols] = encodedText.charAt(i);
        }

        StringBuilder result = new StringBuilder();
        for (int j = 0; j < cols; j++) {
            for (int i = 0; i < rows && j + i < cols; i++) {
                result.append(grid[i][j + i]);
            }
        }

        // Remove trailing spaces
        int len = result.length();
        while (len > 0 && result.charAt(len - 1) == ' ') {
            len--;
        }
        return result.substring(0, len);
    }
}
```
### Algorithm
- Calculate the number of columns in the matrix: `cols = encodedText.length() / rows`.
- If `encodedText` is empty, return an empty string.
- Create a 2D character matrix of size `rows x cols`.
- Populate the matrix by iterating through `encodedText` and filling the matrix row by row. The character at `encodedText[k]` is placed at `matrix[k / cols][k % cols]`.
- Initialize an empty `StringBuilder` to construct the decoded text.
- Iterate through each column index `j` from `0` to `cols - 1`. This index represents the starting column of a diagonal.
- For each starting column `j`, traverse the diagonal by iterating with a row index `i` from `0` to `rows - 1`.
- The cell on the diagonal is at `(i, j + i)`. Check if this cell is within the matrix bounds (i.e., `j + i < cols`).
- If it is in bounds, append the character `matrix[i][j + i]` to the `StringBuilder`.
- After iterating through all diagonals, the `StringBuilder` contains the original text, possibly with trailing spaces.
- Convert the `StringBuilder` to a string and remove any trailing spaces.
- Return the resulting string.

## Optimized Simulation without Matrix
This optimized approach avoids the memory overhead of creating an explicit 2D matrix. Instead of storing the grid, we can directly compute the index of any character in the `encodedText` if we know its row and column position. By applying this calculation during the diagonal traversal, we can build the `originalText` directly, thus saving significant space.
**Time:** O(N), where N is the length of `encodedText`. The nested loops iterate and perform a constant number of operations for each character of the output string. Since the total number of characters in the grid is N, the total time is proportional to N. · **Space:** O(M), where M is the length of the `originalText`. The space is dominated by the `StringBuilder` used to construct the output. In the worst case, `M` can be close to `N`, so the complexity is O(N). This is an improvement over the O(N) auxiliary space of the matrix approach.
**Pros:** More space-efficient as it avoids creating an O(N) auxiliary matrix.; Maintains the optimal O(N) time complexity.
**Cons:** The index calculation `i * cols + j + i` can be slightly less intuitive than a direct 2D array access.
### Explanation
We can improve upon the previous approach by realizing that the intermediate 2D matrix is not strictly necessary. We can calculate the position of any character in the original `encodedText` string directly from its conceptual row and column indices.

The character that would be at `grid[i][j]` is located at index `i * cols + j` in the `encodedText` string. We can leverage this fact to perform the diagonal traversal without ever allocating the matrix.

The decoding logic remains the same: iterate through the diagonals and build the result string. However, instead of `result.append(grid[i][j + i])`, we calculate the index and append directly from the input string: `result.append(encodedText.charAt(i * cols + j + i))`.

This method has the same time complexity but improves the space complexity, making it more efficient for large inputs.

```java
class Solution {
    public String decodeCiphertext(String encodedText, int rows) {
        int n = encodedText.length();
        if (n == 0) {
            return "";
        }
        int cols = n / rows;

        StringBuilder result = new StringBuilder();
        for (int j = 0; j < cols; j++) {
            for (int i = 0; i < rows && j + i < cols; i++) {
                result.append(encodedText.charAt(i * cols + j + i));
            }
        }

        // Remove trailing spaces
        int len = result.length();
        while (len > 0 && result.charAt(len - 1) == ' ') {
            len--;
        }
        return result.substring(0, len);
    }
}
```
### Algorithm
- Calculate the number of columns: `cols = encodedText.length() / rows`.
- If `encodedText` is empty, return an empty string.
- Initialize an empty `StringBuilder`.
- Iterate through each starting column `j` of the diagonals, from `0` to `cols - 1`.
- For each `j`, start a nested loop to traverse the diagonal. The row index `i` goes from `0` to `rows - 1`.
- The column index for the current cell on the diagonal is `current_col = j + i`.
- Check if `current_col` is within the column bounds (`< cols`). If not, this diagonal has ended, so break the inner loop.
- Calculate the 1D index in `encodedText` that corresponds to the matrix cell `(i, current_col)`. The formula is `index = i * cols + current_col`.
- Append the character `encodedText.charAt(index)` to the `StringBuilder`.
- After the loops complete, convert the `StringBuilder` to a string.
- Remove any trailing spaces from the resulting string.
- Return the final string.

# Solutions
### Java

```java
class Solution {
public
  String decodeCiphertext(String encodedText, int rows) {
    StringBuilder ans = new StringBuilder();
    int cols = encodedText.length() / rows;
    for (int j = 0; j < cols; ++j) {
      for (int x = 0, y = j; x < rows && y < cols; ++x, ++y) {
        ans.append(encodedText.charAt(x * cols + y));
      }
    }
    while (ans.length() > 0 && ans.charAt(ans.length() - 1) == ' ') {
      ans.deleteCharAt(ans.length() - 1);
    }
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string decodeCiphertext(string encodedText, int rows) {
    string ans;
    int cols = encodedText.size() / rows;
    for (int j = 0; j < cols; ++j)
      for (int x = 0, y = j; x < rows && y < cols; ++x, ++y)
        ans += encodedText[x * cols + y];
    while (ans.back() == ' ')
      ans.pop_back();
    return ans;
  }
};

```

### Python

```python
class Solution:
    def decodeCiphertext(self, encodedText: str, rows: int) -> str: ans = [] cols = len(encodedText) // rows for j in range(cols): x, y = 0, j while x < rows and y < cols: ans . append(encodedText[x * cols + y]) x, y = x + 1, y + 1 return '' . join(ans). rstrip()

```