LeetCode 1324 - Print Words Vertically

Difficulty: 🟡 Medium
Topics: Array, String, Simulation

Solution

Problem Understanding

The problem requires us to take a string s containing multiple words separated by single spaces and return a list of strings representing the words written vertically. In other words, each column of the output corresponds to characters from the original words at the same position. If a word is shorter than the longest word, missing characters are treated as spaces, but trailing spaces in each vertical string should be removed.

For example, if the input is "HOW ARE YOU", the first vertical string is constructed from the first letters of each word, giving "HAY". The second vertical string is formed from the second letters of each word, giving "ORO", and the third gives "WEU".

Constraints tell us that the input length is relatively small (1 <= s.length <= 200) and only contains uppercase English letters with exactly one space separating words. This guarantees we do not need to handle multiple consecutive spaces or empty words, but we do need to correctly handle words of different lengths.

Important edge cases include strings with single letters, strings where one word is much longer than others, and strings where trailing spaces appear in the vertical output but must be removed.

Approaches

A brute-force approach would involve iterating over each word and trying to build each vertical string one character at a time. This approach would involve nested loops where the outer loop iterates over character positions up to the length of the longest word and the inner loop iterates over the words. For every position, we append the character if it exists or a space if it does not. At the end, we trim trailing spaces from each vertical string. While this is simple, it requires additional steps to manage trailing spaces and may be less clean to implement.

The key insight for the optimal solution is to recognize that we can calculate the maximum word length first and directly iterate column by column. By checking whether a word has a character at the current column index, we append it or a space. After constructing each vertical string, trimming the trailing spaces ensures we satisfy the output constraint. This approach is clean, efficient, and aligns directly with the problem's requirements.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(n * m)	Build each vertical string with nested loops, handle spaces manually
Optimal	O(n * m)	O(n * m)	Precompute max word length, iterate column by column, trim trailing spaces

Here, n is the number of words and m is the length of the longest word.

Algorithm Walkthrough

Split the input string s into a list of words using the space character as a delimiter. This provides direct access to each word.
Compute the maximum word length among all words. This determines the number of vertical strings to produce.
Initialize an empty list result to store the final vertical strings.
Iterate over each column index from 0 to max_length - 1.
For each column index, initialize an empty string vertical_word.
Iterate over each word. If the word has a character at the current column index, append it to vertical_word. If not, append a space.
After processing all words for the current column, strip trailing spaces from vertical_word and append it to result.
After processing all column indices, return the result list.

Why it works: Each vertical string corresponds exactly to a column of characters from the original words. By iterating up to the maximum word length and adding spaces for shorter words, then trimming trailing spaces, we guarantee each vertical string has the correct characters and no trailing spaces. This produces the required vertical representation.

Python Solution

from typing import List

class Solution:
    def printVertically(self, s: str) -> List[str]:
        words = s.split()
        max_length = max(len(word) for word in words)
        result = []
        
        for i in range(max_length):
            vertical_word = ""
            for word in words:
                if i < len(word):
                    vertical_word += word[i]
                else:
                    vertical_word += " "
            result.append(vertical_word.rstrip())
        
        return result

The Python implementation splits the input string into words and calculates the maximum word length. For each column index, it iterates through all words, appending the character at that index if it exists, or a space otherwise. The rstrip() function removes any trailing spaces before appending the string to the result list.

Go Solution

func printVertically(s string) []string {
    words := strings.Fields(s)
    maxLength := 0
    for _, word := range words {
        if len(word) > maxLength {
            maxLength = len(word)
        }
    }

    result := []string{}
    for i := 0; i < maxLength; i++ {
        var sb strings.Builder
        for _, word := range words {
            if i < len(word) {
                sb.WriteByte(word[i])
            } else {
                sb.WriteByte(' ')
            }
        }
        verticalWord := strings.TrimRight(sb.String(), " ")
        result = append(result, verticalWord)
    }

    return result
}

In Go, strings.Fields is used to split the input string into words. We compute the maximum word length, and for each column, we use a strings.Builder to efficiently build the vertical word. Trailing spaces are removed using strings.TrimRight.

Worked Examples

Example 1: "HOW ARE YOU"

Column Index	vertical_word construction	Result after rstrip
0	H A Y	"HAY"
1	O R O	"ORO"
2	W E U	"WEU"

Example 2: "TO BE OR NOT TO BE"

Column Index	vertical_word construction	Result after rstrip
0	T B O N T B	"TBONTB"
1	O E R O O E	"OEROOE"
2	T	" T"

Example 3: "CONTEST IS COMING"

Column Index	vertical_word construction	Result after rstrip
0	C I C	"CIC"
1	O S O	"OSO"
2	N M	"N M"
3	T I	"T I"
4	E N	"E N"
5	S G	"S G"
6	T	"T"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * m)	Iterate over each of n words for each of m positions
Space	O(n * m)	Result list stores n*m characters in the worst case

The time complexity comes from iterating over all words for every character index up to the maximum word length. Space complexity arises from storing the vertical words, which in the worst case can be as large as the original input length.

Test Cases

# Provided examples
assert Solution().printVertically("HOW ARE YOU") == ["HAY","ORO","WEU"]
assert Solution().printVertically("TO BE OR NOT TO BE") == ["TBONTB","OEROOE","   T"]
assert Solution().printVertically("CONTEST IS COMING") == ["CIC","OSO","N M","T I","E N","S G","T"]

# Edge cases
assert Solution().printVertically("A") == ["A"]  # Single character
assert Solution().printVertically("AB CD E") == ["ACE","BD","  "]  # Words of different lengths
assert Solution().printVertically("LONGEST SHORT") == ["LS","HO","NR","GO","ES","ST","T"]  # One longer word

# Maximum length input
assert Solution().printVertically("A" * 200) == ["A" * 200]  # Single very long word

Test	Why
`"HOW ARE YOU"`	Standard example with words of equal length
`"TO BE OR NOT TO BE"`	Mixed word lengths and trailing spaces
`"CONTEST IS COMING"`	Words of different lengths, multiple columns
`"A"`	Minimal input size
`"AB CD E"`	Handling different word lengths and empty spaces
`"LONGEST SHORT"`	Longer first word, shorter second word
`"A"*200`	Max input length to test performance

Edge Cases

Single character input: When s contains only one character, the output should be a list with one string containing that character. This tests minimal input handling.
Different word lengths: If some words are longer than others, intermediate spaces are introduced in vertical strings. The algorithm handles this by appending spaces and then stripping trailing spaces.
Maximum length string: If s is 200 characters long, the algorithm still correctly splits, calculates the maximum word length, and constructs vertical strings without exceeding memory limits or runtime, confirming that the solution scales to the problem's upper constraints.