Last Updated: 5 Mar, 2021

Word Rectangle

Hard

Asked in companies

Solve now

Problem statement

You are given a list of ‘N’ words. Your task is to find the rectangle of the maximum area that can be formed using the list of words zero or more times such that the following conditions hold true:

1. Let ‘W’ be a word formed from reading some row from left to right then ‘W’ must be present in the list.

2. Let ‘W’ be a word formed from reading some column from top to down, then ‘W’ must be present in the list.

Note :

If no such rectangle exists then you need to print 0.

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the length of the list of words.

The next ‘N’ lines contain a single string denoting the word of the given list.

Output Format:

For each test case, print 0 if no such rectangle exists, else print the maximum area of the rectangle that can be formed.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <=  N <= 100
1 <= | WORD[ i ] | <= 10
WORD[ i ] contains only lowercase English letters.

Where ‘T’ is the number of test cases, ‘N’ is the length of the list and ‘WORD[ i ]’ is the word of the list at index i.

Time limit: 1 sec.

Solve now

Approaches

01 Approach

The idea here is to check all rectangles of all possible areas. Let ‘maxlen’ be the maximum length of a word present in the given list. Then max area possible will be less than or equal to maxlen * maxlen because each row and column must represent a word.

So we will be try to form all areas from the maximum possible area of the rectangle that is maxlen * maxlen to 1. First, we will insert all words into a hashmap according to their length. Then we will try to form a word of maximum area. To do this we will keep inserting words row by row from the ‘hashMap’.

Then we check if the current rectangle is valid or not. As all rows are already valid since we have inserted each one of them using hashMap. So we need to check the validity of columns that can be done via trie data structure.

Description of our trie node is shown below.

Our trie data structure basically tells us two things

Whether a given prefix of a word is present in trie or not.
Whether a word present in trie or not. If isEnd of trieNode is true that means a word is ended here.

Algorithm:

Declare a variable to store the maximum possible area of the rectangle, say, ‘maxArea’.
Declare a trie to efficiently check the validity of columns of the matrix and insert all words of the given list into it.
Declare a hash map say, ‘hashMap’ to group all words by their lengths.
Insert all words by their length into the ‘hashMap’.
Insert all words into ‘trie’.
Find a word that has maximum length, say, ‘maxLen’.
Traverse all possible lengths of words from biggest to smallest.
If ‘maxArea’ >= ‘maxLen’ * ‘currentLength’ then break the loop as we have already calculated the maximum possible area of the rectangle. Here ‘currentLength’ denotes the length of the current word.
Try to find the maximum possible area using words of current length by running a ‘dfs’ function.
Finally, return ‘maxArea’.

Description of DFS function:

This function is used to generate all possible rectangles. It will take arguments :

1. ‘word’ – list of current words of the same size.

2. ‘maxArea’ – variable to store ‘maxArea’

3. ‘maxLen’ – Denoting length of maximum word present in the list.

4. ‘temp’ – An array of strings to store current rectangle.

5. ‘trie’ – A data structure to efficiently search a given word.

void dfs(word, maxArea, maxLen, temp, trie)

If the length of word * maxLen <= maxArea then break the recursion. As it shows we have already found a better area.
Traverse through all strings of ‘word’.
Insert current string into ‘temp’ array.
Check if inserting the current string is valid or not by using ‘isValid’ function.’isValid’ function will return two things first if all columns present in temp are also present in trie or not say, ‘colValid’ and if all words present in column are ended at last row or not (This can be done via trie), say ‘allEnd’.
If ‘colValid’ is true then do :
Calculate current area as the number of columns in temp * number of rows in temp, say ‘area’.
If allEnd = true and area > ‘maxArea’ then update ‘maxArea’ by ‘area’.
Since all columns are valid so we can continue inserting the rows by recurring ‘dfs’ function.
Else pop last insert items from temp since all columns are not valid. This is basically the backtracking step.

Description of isValid function :

This function is used to check whether the current rectangle is valid or not. It will check if all elements in column-wise fashion are present in trie or not.

{bool, bool } isValid(current, trie)

Declare a trieNode say ‘cur’.
Declare a variable ‘allEnd’ that denotes all words of the column are ended or not
Traverse current column-wise.
Set ‘cur’ equal to ‘trie’.
Traverse current row-wise.
If the current element is not present in trieNode ‘cur’ then return {false, false } as this arrangement is not valid because all columns are not present in the trie.
Else move ‘cur’ to the next of the current element.
If cur -> isEnd equals to false then set allEnd as false as this word from the current column doesn’t end in trie.
Return {true, allEnd}.

Solve now