Print Words Vertically - Solution & Explanation
Problem Statement
Given a string s. Return all the words vertically in the same order in which they appear in s.
Words are returned as a list of strings, complete with spaces when is necessary. (Trailing spaces are not allowed).
Each word would be put on only one column and that in one column there will be only one word.
Example 1:
Input: s = "HOW ARE YOU" Output: ["HAY","ORO","WEU"] Explanation: Each word is printed vertically. "HAY" "ORO" "WEU"
Example 2:
Input: s = "TO BE OR NOT TO BE" Output: ["TBONTB","OEROOE"," T"] Explanation: Trailing spaces is not allowed. "TBONTB" "OEROOE" " T"
Example 3:
Input: s = "CONTEST IS COMING" Output: ["CIC","OSO","N M","T I","E N","S G","T"]
Constraints:
1 <= s.length <= 200scontains only upper case English letters.- It's guaranteed that there is only one space between 2 words.
Approach Overview
Problem Overview: Given a sentence containing multiple words separated by spaces, you need to print the words vertically. Characters in the same column across words form a new string. Missing characters are treated as spaces, but trailing spaces in each vertical word must be removed.
Approach 1: Column-wise Iteration (O(n * m) time, O(n * m) space)
Split the input string into words and determine the maximum word length. Treat each character index as a column. For column i, iterate through every word and append the character at position i if it exists; otherwise append a space. After constructing the column string, trim trailing spaces before adding it to the result. This approach directly simulates vertical printing using simple iteration over the array of words and character positions. The logic stays straightforward and avoids building an intermediate grid.
Approach 2: Matrix Transposition Approach (O(n * m) time, O(n * m) space)
Create a 2D matrix where each row represents a word and each column represents a character position up to the longest word length. Fill the matrix with characters from each word, padding missing positions with spaces. After building the matrix, transpose it by reading column-by-column to construct vertical strings. Trim trailing spaces before adding each result string. This method models the problem as a grid transformation, similar to matrix operations commonly used in simulation and string manipulation problems.
Recommended for interviews: The column-wise iteration approach is usually preferred. It avoids explicitly storing a full matrix and directly constructs the result with simple loops. Interviewers expect you to recognize that vertical output corresponds to iterating character positions across words. The matrix approach still demonstrates clear thinking and works well as a conceptual stepping stone.
Approach 1: Column-wise Iteration Approach
This approach involves creating a list of strings, where each string represents a vertical column. First, split the string by spaces to get the words. Then calculate the maximum word length. For each column index, iteratively build the column string by taking the character from each word at that column index, if it exists, or space if it doesn’t. Trim trailing spaces from each of column strings.
This solution uses the strtok function to split the input string into words. It stores the words in an array and identifies the longest word's length. The solution then iterates over each character index up to that length, constructing a column by pulling characters from each word. If a word is shorter than the current column index, a space is added. Finally, each column string is printed after trimming trailing spaces.
Complexity
Time complexity: O(n * m), where n is the maximum word length and m is the number of words. Space complexity: O(n * m) as well, assuming all strings have been stored in memory.
Approach 2: Matrix Transposition Approach
Create a matrix of characters where each row represents a word and characters are positioned according to their input order. Then perform a transposition of this matrix, which swaps rows and columns, producing vertical words as rows. Trim the trailing spaces from these rows to complete the solution.
Similar to our previous C implementation, this solution also calculates the maximum word length to determine the number of columns. For each index up to the maximum length, the code assembles and prints a vertical line by drawing from each word, using spaces where necessary. The main difference is in structuring logic towards a matrix analogy concept, emphasizing the transposition of words.
Complexity
Time complexity: O(n * m), where n is the maximum length of words and m is the number of words. Space complexity: O(n * m).
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Column-wise Iteration Approach | Time complexity: O(n * m), where n is the maximum word length and m is the number of words. Space complexity: O(n * m) as well, assuming all strings have been stored in memory. |
| Matrix Transposition Approach | Time complexity: O(n * m), where n is the maximum length of words and m is the number of words. Space complexity: O(n * m). |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Column-wise Iteration | O(n * m) | O(n * m) | Best general solution. Directly builds vertical strings without creating a full matrix. |
| Matrix Transposition | O(n * m) | O(n * m) | Useful when visualizing the problem as a grid or practicing matrix transformation techniques. |
Video Solution
Microsoft Coding Interview Question - Print Words Vertically (LeetCode) • AlgosWithMichael • 4,486 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Print Words Vertically easy or hard?
Print Words Vertically Python or Java solution?
How to solve Print Words Vertically in O(n * m)?
What is the best approach for Print Words Vertically?
What data structure is used in Print Words Vertically?
What is the time complexity of Print Words Vertically?
Is Print Words Vertically asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Print Words Vertically with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor