Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1324. Print Words Vertically - Leetcode Solution

Code Implementation

class Solution:
    def printVertically(self, s: str) -> list[str]:
        words = s.split()
        max_len = max(len(word) for word in words)
        res = []
        for i in range(max_len):
            line = ''
            for word in words:
                if i < len(word):
                    line += word[i]
                else:
                    line += ' '
            res.append(line.rstrip())
        return res
      
class Solution {
public:
    vector<string> printVertically(string s) {
        vector<string> words;
        stringstream ss(s);
        string word;
        while (ss >> word) words.push_back(word);

        int max_len = 0;
        for (auto &w : words) max_len = max(max_len, (int)w.size());
        vector<string> res;
        for (int i = 0; i < max_len; ++i) {
            string line;
            for (auto &w : words) {
                if (i < w.size()) line += w[i];
                else line += ' ';
            }
            while (!line.empty() && line.back() == ' ') line.pop_back();
            res.push_back(line);
        }
        return res;
    }
};
      
class Solution {
    public List<String> printVertically(String s) {
        String[] words = s.split(" ");
        int maxLen = 0;
        for (String word : words) maxLen = Math.max(maxLen, word.length());
        List<String> res = new ArrayList<>();
        for (int i = 0; i < maxLen; ++i) {
            StringBuilder sb = new StringBuilder();
            for (String word : words) {
                if (i < word.length()) sb.append(word.charAt(i));
                else sb.append(' ');
            }
            int end = sb.length();
            while (end > 0 && sb.charAt(end - 1) == ' ') end--;
            res.add(sb.substring(0, end));
        }
        return res;
    }
}
      
var printVertically = function(s) {
    const words = s.split(' ');
    const maxLen = Math.max(...words.map(w => w.length));
    const res = [];
    for (let i = 0; i < maxLen; ++i) {
        let line = '';
        for (let word of words) {
            if (i < word.length) line += word[i];
            else line += ' ';
        }
        res.push(line.replace(/\s+$/g, ''));
    }
    return res;
};

Problem Description

Given a string s consisting of words separated by single spaces, your task is to print the words vertically. Each vertical line should be formed by taking the characters at the same index from each word. If a word is shorter than the current index, use a space character instead. Trailing spaces at the end of each vertical string should be removed. Return the result as a list of strings, each representing a vertical line.

Constraints:
  • Each word contains only uppercase and lowercase English letters.
  • There is exactly one space between words, and no leading or trailing spaces.
  • There is one valid solution for each input.

Thought Process

At first glance, the problem looks like a simple string manipulation task, but it has a subtle twist: instead of printing the words horizontally as usual, we need to print them vertically, aligning each character column-wise.

The naive approach might be to iterate through each character of each word and try to build the vertical strings, but we quickly see that words can have different lengths. This means we need to handle missing characters by substituting spaces, and also ensure we trim trailing spaces for the output.

To optimize, we realize that we can process the input by:
  • Splitting the string into words.
  • Finding the maximum word length, since this determines the number of vertical lines.
  • Building each vertical line by iterating through the words, picking the character if it exists, or a space if it doesn’t.
  • Trimming spaces at the end of each vertical line before adding it to the result.
By breaking the problem into these steps, we can avoid unnecessary complexity and ensure we handle all edge cases.

Solution Approach

The solution can be broken down into the following steps:
  1. Split the Input: Use a string split operation to separate s into a list of words.
  2. Determine the Maximum Word Length: Iterate over the words to find the length of the longest word. This tells us how many vertical lines we need.
  3. Build Each Vertical Line:
    • For each index from 0 to max_len - 1:
    • For each word, if the word has a character at the current index, append it to the current line; otherwise, append a space.
  4. Trim Trailing Spaces: After building each line, remove any spaces at the end before adding it to the result list.
  5. Return the Result: Return the list of vertical lines.
Design Justification:
  • Splitting the string and precomputing the maximum word length ensures we know exactly how many vertical lines to create.
  • Using a nested loop (outer for each character index, inner for each word) allows us to build each vertical line efficiently.
  • Trimming spaces is necessary to match the problem's output requirements.

Example Walkthrough

Sample Input: s = "HOW ARE YOU"

Step 1: Split into words: ["HOW", "ARE", "YOU"]
Step 2: Maximum word length is 3.
Step 3: Build vertical lines:
  • i = 0:
    • H (from "HOW")
    • A (from "ARE")
    • Y (from "YOU")
    • Line: "HAY"
  • i = 1:
    • O (from "HOW")
    • R (from "ARE")
    • O (from "YOU")
    • Line: "ORO"
  • i = 2:
    • W (from "HOW")
    • E (from "ARE")
    • U (from "YOU")
    • Line: "WEU"
Step 4: No trailing spaces need to be trimmed in this example.
Final Output: ["HAY", "ORO", "WEU"]

Time and Space Complexity

Brute-force Approach:
  • If we tried to build each vertical line by scanning every character in the input string for every output line, the time complexity could be as high as O(N * L), where N is the number of words and L is the maximum word length.
Optimized Approach:
  • Splitting the string and finding the maximum word length: O(N * L), since we scan every character once.
  • Building the vertical lines: For each of L lines, we scan all N words, so O(N * L).
  • Trimming each line: Each line is at most N characters, so O(N * L) in total.
  • Total Time Complexity: O(N * L)
  • Space Complexity: O(N * L), for storing the words and the result.

Summary

To solve the "Print Words Vertically" problem, we:
  • Split the input into words
  • Determined the maximum word length to know how many vertical lines are needed
  • Constructed each vertical line by combining corresponding characters, substituting spaces where necessary
  • Trimmed trailing spaces to match the output format
This approach is efficient, easy to understand, and leverages basic string and list operations to solve the problem cleanly and elegantly.