Jobs

Interviews

Discussions

Print Words Vertically

Medium

Guidewire

1 view

Topics:

ArraysStrings

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.

Try coding it in LeetCode

Print Words Vertically

Medium

Guidewire

1 view

Topics:

ArraysStrings

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string 's' and the maximum length of any individual word within 's'?
Can the input string 's' be empty or null? If so, what should the function return in those cases?
Will the input string 's' always contain at least one word, or could it be an empty string containing only spaces?
Are there any characters other than letters and spaces that I need to consider as valid characters in the words?
Should trailing spaces in the resulting vertical strings be removed, or should they be preserved?

Brute Force Solution

Approach

The brute force method tackles this problem by exploring all conceivable arrangements of the letters from the input words. Think of it like physically rearranging letter tiles until we find a valid vertical arrangement. We test each combination to see if it matches the rules.

Here's how the algorithm would work step-by-step:

First, we figure out the length of the longest word because that determines how many rows we'll need.
Then, we create a new empty vertical list of words, one word for each row.
For each column (representing a word in the original input), we grab the letter at the current row position. If the word is shorter than the current row, we use a space.
We add this letter to the end of the row's word.
If a row's word is shorter than the longest word, add spaces to the end of the row's word.
Repeat for each letter position in the original words.
Finally, we remove any trailing spaces from the end of each vertical word we created.

Code Implementation

def print_words_vertically_brute_force(input_string):
    words = input_string.split()
    length_of_longest_word = 0
    for word in words:
        length_of_longest_word = max(length_of_longest_word, len(word))

    vertical_words = ["" for _ in range(length_of_longest_word)]

    # Iterate through each column (original word)
    for word in words:
        #Iterate through each row (character in the current word)
        for index_of_character, character in enumerate(word):

            # Building vertical word by appending char
            vertical_words[index_of_character] += character

        # Pad the rest of the vertical words with spaces
        for index_of_vertical_word in range(len(word), length_of_longest_word):
            vertical_words[index_of_vertical_word] += ' '

    result = []

    # Remove trailing spaces
    for vertical_word in vertical_words:
        result.append(vertical_word.rstrip())

    return result

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each column (word) in the input, where 'n' represents the number of words in the input. Within each column, it iterates up to 'm' times, where 'm' is the length of the longest word, constructing the vertical words. Building each vertical word involves appending characters, a constant-time operation. Therefore, the overall time complexity is proportional to the product of the number of words and the length of the longest word, resulting in O(m*n).

Space Complexity

O(L*W) – The algorithm creates a new list of strings (the 'vertical list of words') to store the vertically arranged words. The number of strings in this list is equal to the length of the longest word (L). Each string can be at most the length of the original input, which can be at most the sum of the lengths of each word (W). Therefore, the space complexity is proportional to the product of the longest word's length and the total number of words, resulting in a space complexity of O(L*W), where L is the length of the longest word and W is the number of words.

Optimal Solution

Approach

The goal is to print words vertically, so think about reading each word one letter at a time, top to bottom. The key is to find the length of the longest word to know how many rows to create. We build each row by picking the corresponding letter from each word, or adding a space if the word is too short.

Here's how the algorithm would work step-by-step:

First, find the longest word in the input. The length of this word will determine how many lines we need to print.
Next, for each line (from the first to the last), we need to construct the line by picking letters from the input words.
To build a line, look at the first word. If the word has a letter for that line (meaning the line number is less than the word's length), take that letter. Otherwise, use a space.
Repeat the previous step for each word in the input. This will create one line of the output.
Repeat the line-building process until you have as many lines as the length of the longest word.
The result is the words printed vertically, with spaces used when a word is shorter than the tallest word.

Code Implementation

def print_words_vertically(input_string):
    words = input_string.split()
    longest_word_length = 0

    for word in words:
        longest_word_length = max(longest_word_length, len(word))

    result = []

    # Iterate up to the length of the longest word.
    for i in range(longest_word_length):
        line = ""
        for word in words:

            # Build each line by picking the ith char.
            if i < len(word):
                line += word[i]
            else:
                line += " "
        
        # Remove trailing spaces to match requirements.
        result.append(line.rstrip())

    return result

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates up to m times, where m is the length of the longest word in the input string array. Inside this outer loop, it iterates through each of the n words in the input array to construct each vertical word. Thus, we are performing m operations within an outer loop that executes n times. This results in a total of approximately m * n operations, leading to a time complexity of O(m*n).

Space Complexity

O(L * W) – The algorithm's primary space consumption stems from storing the vertically arranged words. The plain English explanation suggests constructing each line by picking letters from the input words. In the worst-case scenario where all input words have length L (where L is the length of the longest word), and there are W words in the input, we create a structure to store L lines, with each line containing W characters/spaces. Therefore, the auxiliary space required is proportional to the product of the length of the longest word and the number of words. This gives us a space complexity of O(L * W).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list if the input string is null or empty to avoid null pointer exceptions and handle trivial cases.
Input string with only spaces	Split the string and check if the resulting array is empty or contains only empty strings, returning an empty list.
Input string with a single word	The solution should still correctly process the single word and return it as a single-element list.
Words with varying lengths, including very short and very long words	The solution must correctly pad shorter words with spaces to the length of the longest word to maintain alignment.
Input with leading or trailing spaces in the words	Trim leading/trailing spaces from each word to prevent incorrect padding or alignment issues.
Words containing non-alphanumeric characters (e.g., punctuation)	The solution should process all characters in the words without errors, treating them as part of the vertical strings.
Very large input string leading to memory constraints	Allocate memory efficiently and consider using a StringBuilder or similar approach to minimize memory usage when constructing the output strings.
All words in the input string are the same length	The solution handles this scenario correctly since it iterates to the maximum length and no additional padding is needed.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string 's' and the maximum length of any individual word within 's'?
Can the input string 's' be empty or null? If so, what should the function return in those cases?
Will the input string 's' always contain at least one word, or could it be an empty string containing only spaces?
Are there any characters other than letters and spaces that I need to consider as valid characters in the words?
Should trailing spaces in the resulting vertical strings be removed, or should they be preserved?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, we figure out the length of the longest word because that determines how many rows we'll need.
Then, we create a new empty vertical list of words, one word for each row.
For each column (representing a word in the original input), we grab the letter at the current row position. If the word is shorter than the current row, we use a space.
We add this letter to the end of the row's word.
If a row's word is shorter than the longest word, add spaces to the end of the row's word.
Repeat for each letter position in the original words.
Finally, we remove any trailing spaces from the end of each vertical word we created.

Code Implementation

def print_words_vertically_brute_force(input_string):
    words = input_string.split()
    length_of_longest_word = 0
    for word in words:
        length_of_longest_word = max(length_of_longest_word, len(word))

    vertical_words = ["" for _ in range(length_of_longest_word)]

    # Iterate through each column (original word)
    for word in words:
        #Iterate through each row (character in the current word)
        for index_of_character, character in enumerate(word):

            # Building vertical word by appending char
            vertical_words[index_of_character] += character

        # Pad the rest of the vertical words with spaces
        for index_of_vertical_word in range(len(word), length_of_longest_word):
            vertical_words[index_of_vertical_word] += ' '

    result = []

    # Remove trailing spaces
    for vertical_word in vertical_words:
        result.append(vertical_word.rstrip())

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the longest word in the input. The length of this word will determine how many lines we need to print.
Next, for each line (from the first to the last), we need to construct the line by picking letters from the input words.
To build a line, look at the first word. If the word has a letter for that line (meaning the line number is less than the word's length), take that letter. Otherwise, use a space.
Repeat the previous step for each word in the input. This will create one line of the output.
Repeat the line-building process until you have as many lines as the length of the longest word.
The result is the words printed vertically, with spaces used when a word is shorter than the tallest word.

Code Implementation

def print_words_vertically(input_string):
    words = input_string.split()
    longest_word_length = 0

    for word in words:
        longest_word_length = max(longest_word_length, len(word))

    result = []

    # Iterate up to the length of the longest word.
    for i in range(longest_word_length):
        line = ""
        for word in words:

            # Build each line by picking the ith char.
            if i < len(word):
                line += word[i]
            else:
                line += " "
        
        # Remove trailing spaces to match requirements.
        result.append(line.rstrip())

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list if the input string is null or empty to avoid null pointer exceptions and handle trivial cases.
Input string with only spaces	Split the string and check if the resulting array is empty or contains only empty strings, returning an empty list.
Input string with a single word	The solution should still correctly process the single word and return it as a single-element list.
Words with varying lengths, including very short and very long words	The solution must correctly pad shorter words with spaces to the length of the longest word to maintain alignment.
Input with leading or trailing spaces in the words	Trim leading/trailing spaces from each word to prevent incorrect padding or alignment issues.
Words containing non-alphanumeric characters (e.g., punctuation)	The solution should process all characters in the words without errors, treating them as part of the vertical strings.
Very large input string leading to memory constraints	Allocate memory efficiently and consider using a StringBuilder or similar approach to minimize memory usage when constructing the output strings.
All words in the input string are the same length	The solution handles this scenario correctly since it iterates to the maximum length and no additional padding is needed.