LeetCode #2075 — MEDIUM

Decode the Slanted Ciphertext

Move from brute-force thinking to an efficient approach using core interview patterns strategy.

The Problem

Problem Statement

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.

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.

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:

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:

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:

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 <= 10⁶
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.

Step 01

Brute Force Baseline

Problem summary: 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. 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. 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

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: General problem-solving

Example 1

"ch   ie   pr"
3

Example 2

"iveo    eed   l te   olc"
4

Example 3

"coding"
1

Core Insight

What unlocks the optimal approach

How can you use rows and encodedText to find the number of columns of the matrix?
Once you have the number of rows and columns, you can create the matrix and place encodedText in it. How should you place it in the matrix?
How should you traverse the matrix to "decode" originalText?

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #2075: Decode the Slanted Ciphertext
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();
    }
}

// Accepted solution for LeetCode #2075: Decode the Slanted Ciphertext
func decodeCiphertext(encodedText string, rows int) string {
	ans := []byte{}
	cols := len(encodedText) / rows
	for j := 0; j < cols; j++ {
		for x, y := 0, j; x < rows && y < cols; x, y = x+1, y+1 {
			ans = append(ans, encodedText[x*cols+y])
		}
	}
	for len(ans) > 0 && ans[len(ans)-1] == ' ' {
		ans = ans[:len(ans)-1]
	}
	return string(ans)
}

# Accepted solution for LeetCode #2075: Decode the Slanted Ciphertext
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()

// Accepted solution for LeetCode #2075: Decode the Slanted Ciphertext
/**
 * [2075] Decode the Slanted Ciphertext
 *
 * 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.
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/07/exa11.png" style="width: 300px; height: 185px;" />
 * 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.
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/07/exa12.png" style="width: 300px; height: 200px;" />
 * 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:
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/10/25/desc2.png" style="width: 281px; height: 211px;" />
 * 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:
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/10/26/exam1.png" style="width: 250px; height: 168px;" />
 * 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:
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/10/26/eg2.png" style="width: 300px; height: 51px;" />
 * 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 <= 10^6
 * 	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.
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/decode-the-slanted-ciphertext/
// discuss: https://leetcode.com/problems/decode-the-slanted-ciphertext/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn decode_ciphertext(encoded_text: String, rows: i32) -> String {
        String::new()
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_2075_example_1() {
        let encoded_text = "ch   ie   pr".to_string();
        let rows = 3;

        let result = "cipher".to_string();

        assert_eq!(Solution::decode_ciphertext(encoded_text, rows), result);
    }

    #[test]
    #[ignore]
    fn test_2075_example_2() {
        let encoded_text = "iveo    eed   l te   olc".to_string();
        let rows = 4;

        let result = "i love leetcode".to_string();

        assert_eq!(Solution::decode_ciphertext(encoded_text, rows), result);
    }

    #[test]
    #[ignore]
    fn test_2075_example_3() {
        let encoded_text = "coding".to_string();
        let rows = 1;

        let result = "coding".to_string();

        assert_eq!(Solution::decode_ciphertext(encoded_text, rows), result);
    }
}

// Accepted solution for LeetCode #2075: Decode the Slanted Ciphertext
function decodeCiphertext(encodedText: string, rows: number): string {
    const cols = Math.ceil(encodedText.length / rows);
    const ans: string[] = [];
    for (let k = 0; k <= cols; k++) {
        for (let i = 0, j = k; i < rows && j < cols; i++, j++) {
            ans.push(encodedText[i * cols + j]);
        }
    }
    return ans.join('').trimEnd();
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(n)

Approach Breakdown

BRUTE FORCE

O(n²) time

O(1) space

Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.

OPTIMIZED

O(n) time

O(1) space

Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.

Shortcut: If you are using nested loops on an array, there is almost always an O(n) solution. Look for the right auxiliary state.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.