Largest Square Matrix - Words
Largest Square Matrix - Words
PROBLEM STATEMENT :
The program must accept a string S containing multiple words as the input. The program must form the largest possible square matrix of size N*N based on the following conditions.
- The words of equal length must be used to form the square matrix (i.e., each row in the matrix contains all the characters of a word).
- The words in the given string must be used in the order of their occurrence.
Finally, the program must print the largest possible square matrix as the output. If there are two or more such largest square matrices, the program must print the matrix with the first N words of length N as the output. If it is not possible to form such a matrix, the program must print -1 as the output.
Boundary Condition(s):
1 <= Length of S <= 1000
Input Format:
The first line contains S.
Output Format:
The lines contain the largest possible square matrix or the first line contains -1.
Example Input/Output 1:
Input: ()
book planet MOON earth satellite stars rocket lava Aeroplane Fuel radar
Output:
b o o k
M O O N
l a v a
F u e l
Explanation:
The 4 letter words are book, MOON, lava, and Fuel. These words can form a 4x4 square matrix.
The 5 letter words are earth, stars, and radar. These words cannot form a square matrix.
The 6 letter words are planet and rocket. These words cannot form a square matrix.
The 9 letter words are satellite and Aeroplane. These words cannot form a square matrix.
Hence the output is
M O O N
l a v a
F u e l
Example Input/Output 2:
Input: ()
an the were care one
Output:
-1
Example Input/Output 3:
Input: ()
I like mangoes
Output:
I
Example Input/Output 4:
Input: ()
12 apples 35 grapes 10 tables 40 chairs
Output:
1 2
3 5
1) LEARN THRICE
👇
2) THINK TWICE
👇
3) APPLY ONCE
SOLUTION :
C (Programming Language)
#include<stdio.h>
#include<stdlib.h>
int main()
{
char strs[101][1001];
int freq[1001]={0};
int ind=0,max=-1;
while(scanf("%s",strs[ind])==1)
{
int len = strlen(strs[ind]);
freq[len]++;
if(len > max) max = len;
ind++;
}
for(int i=max;i>=1;i--)
{
if(freq[i]>=i)
{
int rowCount=0;
for(int j=0;j<ind;j++)
{
if(strlen(strs[j])==i)
{
for(int k=0;k<strlen(strs[j]);k++)
{
printf("%c ",strs[j][k]);
}
printf("\n");
rowCount++;
if(rowCount==i) break;
}
}
exit(0);
}
}
printf("-1");
}
C++ (CPP)
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char** argv)
{
string s[101];
int i=1;
cin>>s[0];
int min=s[0].size(),max=s[0].size(),hash[101]={0},words=0,counter=0;
hash[s[0].size()]++;
while(cin>>s[i])
{
if(min>s[i].size())
min=s[i].size();
if(max<s[i].size())
max=s[i].size();
hash[s[i].size()]++;
i++;
}
for(int j=max;j>=min;j--)
{
if(hash[j]>=j)
{
words=j;
break;
}
}
if(words==0){
cout<<-1;
return 0;}
for(int j=0;j<i;j++)
{
if(s[j].size()==words && counter<words)
{
for(int k=0;k<s[j].size();k++)
cout<<s[j][k]<<" ";
cout<<endl;
counter++;
}
}
}
JAVA
import java.util.*;
public class Hello {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] s = sc.nextLine().split(" ");
int[] n = new int[1001];
int max=0;
for(int i=0;i<s.length;i++) {
n[s[i].length()]++;
max=(s[i].length()>max)?s[i].length():max;
}
for(int i=max;i>=1;i--) {
if(n[i]>=i) {
int flag=0;
for(int j=0;j<s.length;j++) {
if(s[j].length()==i) {
flag++;
for(int k=0;k<s[j].length();k++) {
System.out.print(s[j].charAt(k)+" ");
}
System.out.println();
if(flag==i) {
break;
}}}
System.exit(0);
}}
System.out.print("-1");
}}
PYTHON
l=input().strip().split()
d=dict()
for i in l:
if len(i) not in d:
d[len(i)]=[i]
else:
d[len(i)].append(i)
for i in sorted(d,reverse=True):
if len(d[i])>=i:
for j in d[i][:i]:
print(*j,sep=' ')
quit()
print(-1)
Comments
Post a Comment