Word Rectangle

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

1. Whether a given prefix of a word is present in trie or not.
2. 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}.

O(N * (MAX ^ 2) ), where MAX is the maximum length of a word in the given list and ‘N’ is the total number of elements in the given list.

In the worst case when all words of the same length say, ‘MAX’. Then we can have a rectangle of size ‘MAX * MAX’. Our dfs function takes O(N) time as it is checking all words present in the given list. Our ‘isValid function takes O(MAX * MAX) time since the maximum area of the rectangle can be MAX * MAX in the worst case. Also inserting all words in hashMap and Trie takes O(N * MAX) time. 

So overall time complexity = O(N * (MAX ^ 2) ) + O(N * MAX) = O(N * (MAX ^ 2) ).

O( N + SUM ), where ‘SUM’ is the total number of characters present in the given list and ‘N’ is the total number of elements in the given list.

Both trie and hashMap take O(SUM) space since we are inserting all characters of given list in both of them. Also, our dfs function takes O(N) space in form of recursive calls.

So overall space complexity = O(N + SUM ) + O(N) = O(N + SUM).