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^6encodedText consists of lowercase English letters and ' ' onlyencodedText is a valid encoding of some originalText that has no trailing spaces1 <= rows <= 1000exactly one originalText produces encodedText
Hints for Decode the Slanted Ciphertext
Hint 1
The number of columns follows directly from the input:
cols = encodedText.length / rows.Hint 2
Cell
(r, c)of the grid isencodedText[r * cols + c].Hint 3
Read the diagonal starting at
(0, c)for everycfrom 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
- Let
cols = encodedText.length / rows; cell(r, c)sits at indexr * cols + c. - For each starting column
cfrom 0 tocols - 1, walk(0, c), (1, c+1), (2, c+2), …while both the row and the column stay inside the grid, appending each character. - 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