Print Words Vertically
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach conceptualizes the problem as transposing a matrix. It first arranges the words into a 2D grid where rows represent words and columns represent character indices. Then, it reads the grid column by column to form the vertical words. This method is intuitive but may use more memory due to the intermediate grid structure.
Algorithm
- Split the input string
sinto an array ofwords. - Determine the number of words (
numWords) and the length of the longest word (maxLength). - Create a 2D character grid of size
maxLengthrows andnumWordscolumns, initializing all cells with spaces. - Populate the grid by placing the characters of each word into the corresponding columns. For a word
words[j], itsi-th character goes intogrid[i][j]. - Create a new list of strings,
result. - Iterate through each row of the grid. For each row, convert the character array into a string.
- Trim any trailing spaces from the newly created string.
- Add the trimmed string to the
resultlist. - Return the
resultlist.
Walkthrough
The core idea is to create an explicit grid (a 2D character array) to represent the vertically aligned words.
First, we split the input string s into an array of words. We then find the dimensions of our grid: the number of rows will be the length of the longest word (maxLength), and the number of columns will be the number of words (numWords).
We create a char grid of size maxLength x numWords and initialize it with space characters. This ensures that any position not occupied by a letter from a word will correctly be a space.
Next, we populate this grid. We iterate through our array of words. For each word at index j, we iterate through its characters. The character at index i of the word is placed at grid[i][j]. This effectively transposes the words into the grid.
Finally, we iterate through the rows of the grid. Each row represents a complete vertical word. We convert each row (which is a char array) into a String. Since the problem states that trailing spaces are not allowed, we trim these from the end of each string before adding it to our final result list.
import java.util.ArrayList;import java.util.List;import java.util.Arrays; class Solution { public List<String> printVertically(String s) { String[] words = s.split(" "); int numWords = words.length; int maxLength = 0; for (String word : words) { maxLength = Math.max(maxLength, word.length()); } // Create and initialize the grid with spaces char[][] grid = new char[maxLength][numWords]; for (char[] row : grid) { Arrays.fill(row, ' '); } // Populate the grid (transposed) for (int j = 0; j < numWords; j++) { // Iterate through words (columns of grid) String word = words[j]; for (int i = 0; i < word.length(); i++) { // Iterate through chars (rows of grid) grid[i][j] = word.charAt(i); } } // Build result strings from grid rows List<String> result = new ArrayList<>(); for (int i = 0; i < maxLength; i++) { String verticalWord = new String(grid[i]); // Trim trailing spaces manually int lastNonSpace = verticalWord.length() - 1; while (lastNonSpace >= 0 && verticalWord.charAt(lastNonSpace) == ' ') { lastNonSpace--; } result.add(verticalWord.substring(0, lastNonSpace + 1)); } return result; }}Complexity
Time
O(M * N), where `M` is the length of the longest word and `N` is the number of words. The total time is the sum of splitting the string (`O(L)`), initializing the grid (`O(M * N)`), populating the grid (`O(L)`), and building the final strings (`O(M * N)`).
Space
O(M * N), where `M` is the length of the longest word and `N` is the number of words. This is dominated by the space required for the `char[][]` grid. Additional space is used for the `words` array (`O(L)`, where `L` is the length of `s`) and the result list (`O(M * N)`).
Trade-offs
Pros
The logic is easy to visualize as a matrix transposition problem.
Separates the data population from the result construction, which can make the code easier to read for some developers.
Cons
Requires extra space for the 2D grid, which can be significant if the number of words or the max length is large.
Involves multiple passes over the data structure (initialize, populate, read), which might be slightly less performant than a single-pass approach.
Solutions
Solution
class Solution { public List < String > printVertically ( String s ) { String [] words = s . split ( " " ); int n = 0 ; for ( var w : words ) { n = Math . max ( n , w . length ()); } List < String > ans = new ArrayList <>(); for ( int j = 0 ; j < n ; ++ j ) { StringBuilder t = new StringBuilder (); for ( var w : words ) { t . append ( j < w . length () ? w . charAt ( j ) : ' ' ); } while ( t . length () > 0 && t . charAt ( t . length () - 1 ) == ' ' ) { t . deleteCharAt ( t . length () - 1 ); } ans . add ( t . toString ()); } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.