Decode the Slanted Ciphertext

Medium
1232.

Decode the Slanted Ciphertext

Decode the Slanted Ciphertext is a medium coding problem on strings and simulation, asked in Amazon and Google interviews.

A message originalText (lowercase letters and spaces, with no trailing spaces) was encrypted with a slanted transposition using a grid with a fixed number of rows:

  • The text is written along diagonals that run down and to the right. The first diagonal starts at the top-left cell (0, 0) and takes characters until it reaches the last row; the next diagonal starts at (0, 1), then (0, 2), and so on.
  • The grid has the fewest columns for which the whole text fits — its rightmost column is not empty.
  • Every cell left unused holds a space ' '.

The ciphertext encodedText is the grid read row by row, left to right, top row first.

Given encodedText and rows, return originalText.

Example 1

Input
encodedText = "ceao o i dkr", rows = 3
Output
code kairo
Explanation
The grid is 3 × 5: rows `"ceao "`, `" o i "` and `" dkr"`. Reading the diagonals from columns 0..4 gives `"cod"`, `"e k"`, `"air"`, `"o "`, `" "`; dropping the trailing spaces leaves `"code kairo"`.

Example 2

Input
encodedText = "kairo", rows = 1
Output
kairo
Explanation
With one row nothing moves.

Example 3

Input
encodedText = "a b ", rows = 3
Output
ab

Constraints

  • 1 <= encodedText.length <= 10^6
  • encodedText consists of lowercase English letters and ' ' only
  • encodedText is a valid encoding of some originalText that has no trailing spaces
  • 1 <= rows <= 1000
  • exactly one originalText produces encodedText
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} encodedText
 * @param {number} rows
 * @return {string}
 */
var decodeCiphertext = function(encodedText, rows) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Decode the Slanted Ciphertext — Problem & Solution

Decode the Slanted Ciphertext solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Decode the Slanted Ciphertext is a medium coding problem on strings and simulation, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Simulation
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A message originalText (lowercase letters and spaces, with no trailing spaces) was encrypted with a slanted transposition using a grid with a fixed number of rows:

  • The text is written along diagonals that run down and to the right. The first diagonal starts at the top-left cell (0, 0) and takes characters until it reaches the last row; the next diagonal starts at (0, 1), then (0, 2), and so on.
  • The grid has the fewest columns for which the whole text fits — its rightmost column is not empty.
  • Every cell left unused holds a space ' '.

The ciphertext encodedText is the grid read row by row, left to right, top row first.

Given encodedText and rows, return originalText.

Example 1

Input: encodedText = "ceao  o i   dkr", rows = 3
Output: code kairo
Explanation: The grid is 3 × 5: rows `"ceao "`, `" o i "` and `"  dkr"`. Reading the diagonals from columns 0..4 gives `"cod"`, `"e k"`, `"air"`, `"o "`, `" "`; dropping the trailing spaces leaves `"code kairo"`.

Example 2

Input: encodedText = "kairo", rows = 1
Output: kairo
Explanation: With one row nothing moves.

Example 3

Input: encodedText = "a  b  ", rows = 3
Output: ab

Constraints

  • 1 <= encodedText.length <= 10^6
  • encodedText consists of lowercase English letters and ' ' only
  • encodedText is a valid encoding of some originalText that has no trailing spaces
  • 1 <= rows <= 1000
  • exactly one originalText produces encodedText

Hints for Decode the Slanted Ciphertext

  1. Hint 1

    The number of columns follows directly from the input: cols = encodedText.length / rows.

  2. Hint 2

    Cell (r, c) of the grid is encodedText[r * cols + c].

  3. Hint 3

    Read the diagonal starting at (0, c) for every c from left to right, then strip the trailing spaces that came from the padding.

How to solve Decode the Slanted Ciphertext

Rebuild the grid's coordinates from the ciphertext and read the diagonals back in the order they were written; only the padding at the end needs removing.

Approach

  1. Let cols = encodedText.length / rows; cell (r, c) sits at index r * cols + c.
  2. For each starting column c from 0 to cols - 1, walk (0, c), (1, c+1), (2, c+2), … while both the row and the column stay inside the grid, appending each character.
  3. Remove the trailing spaces from the result and return it.

Why it works

Encryption wrote character k of the text onto diagonal k / rows at row k % rows, so reading diagonals in order of their starting column, top to bottom, visits the text in its original order. The diagonals also pass through unused cells, which hold spaces; all of those come after the last character of the text, because the text fills diagonals in order. Since the original text has no trailing spaces, stripping them recovers it exactly.

Complexity

  • Time — O(n) where n is the ciphertext length
  • Space — O(n) for the output

Pitfalls

  • Strip only trailing spaces — spaces inside the text are part of the message.
  • A diagonal stops at the right edge as well as at the bottom row.
  • There is no need to materialise the grid; index arithmetic is enough.

Reference solution

Python

def decodeCiphertext(encodedText: str, rows: int) -> str:
    n = len(encodedText)
    cols = n // rows
    out = []
    for c in range(cols):
        r, j = 0, c
        while r < rows and j < cols:
            out.append(encodedText[r * cols + j])
            r += 1
            j += 1
    return "".join(out).rstrip(" ")

Java

public static String decodeCiphertext(String encodedText, int rows) {
    int n = encodedText.length(), cols = n / rows;
    StringBuilder sb = new StringBuilder();
    for (int c = 0; c < cols; c++) {
        for (int r = 0, j = c; r < rows && j < cols; r++, j++) sb.append(encodedText.charAt(r * cols + j));
    }
    int k = sb.length();
    while (k > 0 && sb.charAt(k - 1) == ' ') k--;
    sb.setLength(k);
    return sb.toString();
}

C++

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

JavaScript

var decodeCiphertext = function(encodedText, rows) {
    var cols = encodedText.length / rows;
    var out = [];
    for (var c = 0; c < cols; c++) {
        for (var r = 0, j = c; r < rows && j < cols; r++, j++) out.push(encodedText[r * cols + j]);
    }
    var k = out.length;
    while (k > 0 && out[k - 1] === " ") k--;
    return out.slice(0, k).join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings