We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Decode the Slanted Ciphertext

Number: 2197

Difficulty: Medium

Paid? No

Companies: Grammarly, Amazon

Problem Description

Given an encoded string encodedText and an integer rows, determine the original string originalText that was encoded using a slanted transposition cipher. In this cipher, originalText is placed diagonally in a matrix with a fixed number of rows, and the remaining empty cells are filled with spaces. The encodedText is then generated by reading the entire matrix row by row. The goal is to reconstruct originalText by simulating the reverse of this process; note that the resulting originalText does not have trailing spaces.

Key Insights

  • The encodedText represents a 2D matrix filled row-wise.
  • The number of columns in the matrix can be calculated as len(encodedText) / rows.
  • The original string was placed in the matrix diagonally from top left to bottom right.
  • To decode, we traverse the matrix diagonally starting from each column of the first row.
  • Finally, trailing spaces (if any) must be removed from the result since originalText does not include them.

Space and Time Complexity

Time Complexity: O(n), where n is the length of encodedText, because every character is processed once. Space Complexity: O(n), which is used to store the output and potentially the reconstructed matrix.

Solution

The solution begins by computing the number of columns as len(encodedText) divided by rows. We can simulate the matrix by imagining its row-wise filling. For each starting column in the first row, we traverse diagonally (moving one row down and one step to the right) and append the corresponding characters to build originalText. It is crucial to trim any trailing spaces from the resulting string, as per the problem requirements. This method leverages simple iteration and index arithmetic on a virtual 2D grid.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with detailed comments.

# Function to decode the slanted ciphertext
def decodeCiphertext(encodedText: str, rows: int) -> str:
    # Calculate the number of columns in the matrix
    n = len(encodedText) // rows  
    result = []  # List to store characters from the original text
    
    # Loop over each starting column in the first row
    for start_col in range(n):
        r, c = 0, start_col
        # Traverse diagonally: move down one row and one column at a time
        while r < rows and c < n:
            # The index in the row-wise filled encodedText
            result.append(encodedText[r * n + c])
            r += 1
            c += 1
    
    # Join the characters into a string and remove trailing spaces
    return "".join(result).rstrip()

# Example usage:
# print(decodeCiphertext("ch   ie   pr", 3))
← Back to All Questions