Decode the Slanted Ciphertext

medium string matrix simulation

Problem

An original string was encoded with a slanted transposition cipher: it was written diagonally (top-left to bottom-right) into a matrix with a fixed number of rows, empty cells padded with spaces, then read out row-by-row to form encodedText. Given encodedText and rows, recover the original string. The original has no trailing spaces, and the answer is unique.

InputencodedText = "ch ie pr", rows = 3

Output"cipher"

The 3×4 matrix reads "cipher" along its diagonals.

InputencodedText = "coding", rows = 1

Output"coding"

With one row the matrix is a single line, so the text is unchanged.

encodedText (spaces matter)

rows

def decode_ciphertext(encoded_text, rows):
    n = len(encoded_text)
    cols = n // rows
    result = []
    for start in range(cols):
        r, c = 0, start
        while r < rows and c < cols:
            result.append(encoded_text[r * cols + c])
            r += 1
            c += 1
    return "".join(result).rstrip()

function decodeCiphertext(encodedText, rows) {
  const n = encodedText.length;
  const cols = Math.floor(n / rows);
  let result = "";
  for (let start = 0; start < cols; start++) {
    let r = 0, c = start;
    while (r < rows && c < cols) {
      result += encodedText[r * cols + c];
      r++;
      c++;
    }
  }
  return result.replace(/\s+$/, "");
}

String decodeCiphertext(String encodedText, int rows) {
    int n = encodedText.length();
    int cols = n / rows;
    StringBuilder result = new StringBuilder();
    for (int start = 0; start < cols; start++) {
        int r = 0, c = start;
        while (r < rows && c < cols) {
            result.append(encodedText.charAt(r * cols + c));
            r++;
            c++;
        }
    }
    return result.toString().replaceAll("\\s+$", "");
}

string decodeCiphertext(string encodedText, int rows) {
    int n = encodedText.size();
    int cols = n / rows;
    string result;
    for (int start = 0; start < cols; start++) {
        int r = 0, c = start;
        while (r < rows && c < cols) {
            result += encodedText[r * cols + c];
            r++;
            c++;
        }
    }
    while (!result.empty() && result.back() == ' ') result.pop_back();
    return result;
}

Explanation

Encoding wrote the text diagonally into a matrix and then read it row-by-row. Decoding just reverses that: rebuild the matrix from the row-wise string, then read it back along the same diagonals.

The matrix has rows rows. Since encodedText is exactly the matrix flattened row-by-row, its length n divides evenly into rows, giving cols = n / rows columns. Cell (r, c) therefore lives at index r * cols + c in encodedText — no actual 2-D array is needed.

Each diagonal starts in the top row at some column start and walks down-right: (0, start), (1, start+1), (2, start+2), … stopping when it falls off the bottom (r == rows) or off the right edge (c == cols). Visiting start = 0, 1, …, cols−1 in order reads every character of the original text in its original order.

Finally we strip trailing spaces. The padding spaces only ever sit at the end of the decoded stream (the original text has no trailing spaces and the rightmost column is non-empty by construction), so a single rstrip recovers the answer.

For "ch ie pr" with rows = 3 we get a 3×4 matrix. The diagonals spell c, i, p, h, e, r followed by padding spaces, so the original text is "cipher".

Time: O(n) Space: O(n)