Print Words Vertically solution and explanation
5 more videos on this problem
Microsoft Coding Interview Question - Print Words Vertically (LeetCode)AlgosWithMichael · 14:51 · 4K views
leetcode 1324 || Weekly Contest 172 || Print Words Vertically || Medium question || latest questioncode Explainer · 7:22 · 1K views
Print Words Vertically (Leetcode 1324)Coding Interviews · 9:57 · 1K views
leetcode 1324 | Print Words Vertically | leetcode Medium Level QuestionEduEverybody · 22:18 · 482 views
1324. Print Words Vertically leetcodeRoushan Kumar · 12:23 · 339 views
[LeetCode] 1324, Print Words Vertically개발자영맨(bluedawnstar) · 16:07 · 300 views
The 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 <= 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.
def print_vertically(s):
words = s.split()
max_len = max(len(word) for word in words)
result = []
for i in range(max_len):
column = ''.join((word[i] if i < len(word) else ' ') for word in words)
result.append(column.rstrip())
return result
# Example Usage
input_string = "HOW ARE YOU"
output = print_vertically(input_string)
for line in output:
print(f'"{line}"')import java.util.ArrayList;
import java.util.List;
public class Solution {
public static List<String> printVertically(String s) {
String[] words = s.split(" ");
int maxLen = 0;
for (String word : words) {
maxLen = Math.max(maxLen, word.length());
}
List<String> result = 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(' ');
}
while (sb.length() > 0 && sb.charAt(sb.length() - 1) == ' ') {
sb.deleteCharAt(sb.length() - 1);
}
result.add(sb.toString());
}
return result;
}
public static void main(String[] args) {
String input = "HOW ARE YOU";
List<String> result = printVertically(input);
for (String line : result) {
System.out.println('"' + line + '"');
}
}
}#include <iostream>
#include <vector>
#include <string>
#include <sstream>
std::vector<std::string> printVertically(std::string s) {
std::vector<std::string> words;
std::istringstream stream(s);
std::string word;
size_t max_len = 0;
while (stream >> word) {
words.push_back(word);
max_len = std::max(max_len, word.length());
}
std::vector<std::string> result(max_len, std::string(words.size(), ' '));
for (size_t i = 0; i < words.size(); ++i) {
for (size_t j = 0; j < words[i].length(); ++j) {
result[j][i] = words[i][j];
}
}
for (auto &line : result) {
while (!line.empty() && line.back() == ' ') line.pop_back();
}
return result;
}
int main() {
std::string s = "HOW ARE YOU";
std::vector<std::string> result = printVertically(s);
for (const std::string &line : result) {
std::cout << '"' << line << '"' << std::endl;
}
return 0;
}function printVertically(s) {
let words = s.split(' ');
let maxLen = Math.max(...words.map(word => word.length));
let result = [];
for (let i = 0; i < maxLen; i++) {
let column = words.map(word => (i < word.length ? word[i] : ' ')).join('');
result.push(column.trimEnd());
}
return result;
}
// Example usage
let input = "HOW ARE YOU";
let output = printVertically(input);
output.forEach(line => console.log('"' + line + '"'));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void printVertically(char *s) {
char *words[200];
int word_count = 0;
int max_len = 0;
char *token = strtok(s, " ");
while (token) {
words[word_count++] = token;
if (strlen(token) > max_len) {
max_len = strlen(token);
}
token = strtok(NULL, " ");
}
for (int i = 0; i < max_len; i++) {
char column[201] = {0};
int k = 0;
for (int j = 0; j < word_count; j++) {
if (i < strlen(words[j]))
column[k++] = words[j][i];
else
column[k++] = ' ';
}
while (k > 0 && column[k - 1] == ' ') k--;
column[k] = '\0';
printf("%s\n", column);
}
}
int main() {
char input[] = "HOW ARE YOU";
printVertically(input);
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static IList<string> PrintVertically(string s) {
string[] words = s.Split(' ');
int maxLen = 0;
foreach (string word in words) {
maxLen = Math.Max(maxLen, word.Length);
}
List<string> result = new List<string>();
for (int i = 0; i < maxLen; i++) {
char[] column = new char[words.Length];
for (int j = 0; j < words.Length; j++) {
column[j] = (i < words[j].Length) ? words[j][i] : ' ';
}
result.Add(new String(column).TrimEnd());
}
return result;
}
static void Main() {
string input = "HOW ARE YOU";
IList<string> result = PrintVertically(input);
foreach (var line in result) {
Console.WriteLine('"' + line + '"');
}
}
}The Python solution splits the string to get individual words and calculates the length of the longest word. It builds each vertical string using a generator expression within a join operation, appending spaces where needed. Each assembled column is then stripped of trailing spaces before being appended to the result list.
Time complexity: O(n * m), where n is the maximum length of words and m is the total number of words. Space complexity: O(n * m).
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.
def print_vertically(s):
words = s.split()
max_len = max(len(word) for word in words)
result = []
for i in range(max_len):
column = ''.join(word[i] if i < len(word) else ' ' for word in words)
result.append(column.rstrip())
return result
# Example
input_string = "HOW ARE YOU"
output = print_vertically(input_string)
for line in output:
print(f'"{line}"')import java.util.ArrayList;
import java.util.List;
public 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> result = 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(' ');
}
while (sb.length() > 0 && sb.charAt(sb.length() - 1) == ' ') {
sb.deleteCharAt(sb.length() - 1);
}
result.add(sb.toString());
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
String input = "HOW ARE YOU";
List<String> result = solution.printVertically(input);
for (String line : result) {
System.out.println('"' + line + '"');
}
}
}#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
vector<string> printVertically(string s) {
vector<string> words;
stringstream ss(s);
string word;
size_t max_len = 0;
while (ss >> word) {
words.push_back(word);
max_len = max(max_len, word.length());
}
vector<string> result(max_len, string(words.size(), ' '));
for (size_t i = 0; i < words.size(); ++i) {
for (size_t j = 0; j < words[i].length(); ++j) {
result[j][i] = words[i][j];
}
}
for (auto &line : result) {
while (!line.empty() && line.back() == ' ') line.pop_back();
}
return result;
}
int main() {
string input = "HOW ARE YOU";
vector<string> result = printVertically(input);
for (const string &line : result) {
cout << '"' << line << '"' << endl;
}
return 0;
}function printVertically(s) {
const words = s.split(' ');
const maxLen = Math.max(...words.map(word => word.length));
const result = [];
for (let i = 0; i < maxLen; i++) {
let column = words.map(word => (i < word.length ? word[i] : ' ')).join('');
result.push(column.trimEnd());
}
return result;
}
// Example usage
const input = "HOW ARE YOU";
const output = printVertically(input);
output.forEach(line => console.log('"' + line + '"'));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Utility function to find maximum word length
int maxWordLength(char **words, int numWords) {
int max = 0;
for (int i = 0; i < numWords; i++) {
int len = strlen(words[i]);
if (len > max) max = len;
}
return max;
}
void printVertically(char *s) {
char *words[100];
int word_count = 0;
char *token = strtok(s, " ");
while (token) {
words[word_count++] = token;
token = strtok(NULL, " ");
}
int max_len = maxWordLength(words, word_count);
for (int i = 0; i < max_len; i++) {
char column[201] = {0};
int k = 0;
for (int j = 0; j < word_count; j++) {
if (i < strlen(words[j]))
column[k++] = words[j][i];
else
column[k++] = ' ';
}
while (k > 0 && column[k - 1] == ' ') k--;
column[k] = '\0';
printf("%s\n", column);
}
}
int main() {
char input[] = "HOW ARE YOU";
printVertically(input);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<string> PrintVertically(string s) {
string[] words = s.Split(' ');
int maxLen = 0;
foreach (string word in words) {
maxLen = Math.Max(maxLen, word.Length);
}
List<string> result = new List<string>();
for (int i = 0; i < maxLen; i++) {
char[] column = new char[words.Length];
for (int j = 0; j < words.Length; j++) {
column[j] = (i < words[j].Length) ? words[j][i] : ' ';
}
result.Add(new string(column).TrimEnd());
}
return result;
}
public static void Main() {
Solution solution = new Solution();
string input = "HOW ARE YOU";
IList<string> result = solution.PrintVertically(input);
foreach (string line in result) {
Console.WriteLine('"' + line + '"');
}
}
}The Python solution aligns input into a conceptual matrix and extracts transposed rows to represent columns transformed into vertical words. By strategically employing list comprehension, the approach efficiently compares indices for integrity while minimizing unnecessary space usage.
Time complexity: O(n * m), with n as longest word length and m as word count. Space complexity: O(n * m).
Approach 3: Default Approach
func printVertically(s string) (ans []string) {
words := strings.Split(s, " ")
n := 0
for _, w := range words {
n = max(n, len(w))
}
for j := 0; j < n; j++ {
t := []byte{}
for _, w := range words {
if j < len(w) {
t = append(t, w[j])
} else {
t = append(t, ' ')
}
}
for len(t) > 0 && t[len(t)-1] == ' ' {
t = t[:len(t)-1]
}
ans = append(ans, string(t))
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Column-wise Iteration Approach | Time complexity: O(n * m), where n is the maximum length of words and m is the total number of words. Space complexity: O(n * m). |
| Matrix Transposition Approach | Time complexity: O(n * m), with n as longest word length and m as word count. Space complexity: O(n * m). |
| Default Approach | – |
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. |
Frequently asked questions
Is Print Words Vertically easy or hard?
Print Words Vertically is rated Medium difficulty on LeetCode. The algorithm itself is simple, but handling missing characters, padding spaces, and trimming trailing spaces correctly can cause edge case mistakes.
Print Words Vertically Python or Java solution?
Python and Java implementations typically follow the column-wise iteration approach. Python uses lists and string joins for clean construction, while Java often uses StringBuilder to append characters efficiently during column traversal.
How to solve Print Words Vertically in O(n * m)?
Split the input sentence into words and compute the longest word length. For each column index from 0 to max length - 1, iterate through all words and append the character if it exists or a space otherwise. Remove trailing spaces from the constructed string before adding it to the result list.
What is the best approach for Print Words Vertically?
The column-wise iteration approach is the most practical solution. Split the sentence into words, find the maximum word length, then iterate column by column and collect characters from each word. This produces vertical strings directly while trimming trailing spaces. Time complexity is O(n * m) where n is the number of words and m is the maximum word length.
What data structure is used in Print Words Vertically?
The solution mainly uses arrays or lists to store words after splitting the input string. Some implementations also simulate a 2D matrix when using the matrix transposition approach. String builders or mutable strings are often used to efficiently construct the vertical outputs.
What is the time complexity of Print Words Vertically?
The time complexity is O(n * m). Each column up to the maximum word length is processed, and for every column you iterate through all words. Space complexity is also O(n * m) due to storing the output strings.
Is Print Words Vertically asked at Google, Amazon, or Meta?
String formatting and simulation problems like Print Words Vertically appear in coding interviews at large tech companies including Amazon and Google. They test attention to detail, handling uneven string lengths, and correct iteration logic.