# Print Words Vertically
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/print-words-vertically)
Canonical: https://scaleengineer.com/dsa/problems/print-words-vertically
**Data structures:** Array, String
**Companies:** [Guidewire](https://scaleengineer.com/companies/guidewire)
---
## Problem
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 <= 200`
* `s` contains only upper case English letters.
* It's guaranteed that there is only one space between 2 words.

# Approaches
## Grid-based Transposition
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.
**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)`).
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Split the input string `s` into an array of `words`.
- Determine the number of words (`numWords`) and the length of the longest word (`maxLength`).
- Create a 2D character grid of size `maxLength` rows and `numWords` columns, initializing all cells with spaces.
- Populate the grid by placing the characters of each word into the corresponding columns. For a word `words[j]`, its `i`-th character goes into `grid[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 `result` list.
- Return the `result` list.

## Direct Column-wise Construction
This approach directly simulates the process of building the vertical words without creating an intermediate 2D grid. It first splits the input string into words and determines the maximum word length. Then, it iterates from the first character index to the maximum length index, constructing each vertical word column by column. This method is generally more efficient in terms of memory and speed.
**Time:** O(M * N), where `M` is the length of the longest word and `N` is the number of words. We iterate `M` times, and for each iteration, we loop through `N` words. String building and trimming operations inside the loop contribute to this complexity. The initial split and find max length operations take `O(L)`, where `L` is the length of `s`. · **Space:** O(M * N), where `M` is the length of the longest word and `N` is the number of words. The space is primarily used for the `words` array (`O(L)`) and the `result` list, which stores the output of size `O(M * N)`.
**Pros:** Memory efficient as it avoids creating a large intermediate 2D data structure.; Generally faster due to better data locality and fewer passes over the data.; The logic directly maps to the construction of the output, making it conceptually straightforward.
**Cons:** The logic of building strings in nested loops might be slightly less intuitive to visualize than a grid transposition for some.
### Explanation
This approach is a more direct simulation of the required output. It avoids creating a full intermediate grid, thus saving space and potentially time.

First, we split the input string `s` into an array of `words`. We then iterate through this array to find the length of the longest word, `maxLength`. This value determines how many vertical strings we need to generate.

We then loop from `i = 0` to `maxLength - 1`. Each `i` corresponds to a row in the final output list. Inside this loop, we build the string for that row. We use a `StringBuilder` for efficient string construction.

For each `i`, we iterate through all the `words`. We check if the current word has a character at index `i`. If `i` is less than the word's length, we append `word.charAt(i)` to our `StringBuilder`. If the word is shorter, it means we need a space in that position for alignment, so we append a space character.

After iterating through all the words, the `StringBuilder` contains the complete vertical string for the `i`-th row, but it might have trailing spaces (e.g., if the last few words in the input were shorter than others). We must remove these trailing spaces. A simple way is to find the index of the last non-space character and create a substring. Finally, we add this cleaned-up string to our result list.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> printVertically(String s) {
        String[] words = s.split(" ");
        int maxLength = 0;
        for (String word : words) {
            maxLength = Math.max(maxLength, word.length());
        }

        List<String> result = new ArrayList<>();
        for (int i = 0; i < maxLength; i++) {
            StringBuilder verticalWord = new StringBuilder();
            for (String word : words) {
                if (i < word.length()) {
                    verticalWord.append(word.charAt(i));
                } else {
                    verticalWord.append(" ");
                }
            }
            
            // Trim trailing spaces from the StringBuilder
            int lastNonSpace = verticalWord.length() - 1;
            while (lastNonSpace >= 0 && verticalWord.charAt(lastNonSpace) == ' ') {
                lastNonSpace--;
            }
            result.add(verticalWord.substring(0, lastNonSpace + 1));
        }
        return result;
    }
}
```
### Algorithm
- Split the input string `s` into an array of `words`.
- Find the `maxLength` of the longest word in the `words` array.
- Initialize an empty list `result` to store the final vertical words.
- Loop with an index `i` from `0` to `maxLength - 1`. This index represents the character position in each word (the column).
- Inside the loop, create a `StringBuilder` to construct the current vertical word.
- Iterate through each `word` in the `words` array.
- If the current character index `i` is less than the length of the `word`, append `word.charAt(i)` to the `StringBuilder`.
- Otherwise, the word is too short, so append a space `' '`.
- After iterating through all words, the `StringBuilder` holds the vertical word for column `i`.
- Trim any trailing spaces from the string generated by the `StringBuilder`.
- Add the trimmed string to the `result` list.
- After the outer loop completes, return the `result` list.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
class Solution { public: vector < string > printVertically ( string s ) { stringstream ss ( s ); vector < string > words ; string word ; int n = 0 ; while ( ss >> word ) { words . emplace_back ( word ); n = max ( n , ( int ) word . size ()); } vector < string > ans ; for ( int j = 0 ; j < n ; ++ j ) { string t ; for ( auto & w : words ) { t += j < w . size () ? w [ j ] : ' ' ; } while ( t . size () && t . back () == ' ' ) { t . pop_back (); } ans . emplace_back ( t ); } return ans ; } };
```

### Python

```python
class Solution : def printVertically ( self , s : str ) -> List [ str ]: words = s . split () n = max ( len ( w ) for w in words ) ans = [] for j in range ( n ): t = [ w [ j ] if j < len ( w ) else ' ' for w in words ] while t [ - 1 ] == ' ' : t . pop () ans . append ( '' . join ( t )) return ans
```