{"id":"29284a4a-7f49-47eb-a8f7-6a3a00063a5e","name":"Word Wrap","description":"1. You are given a number N representing number of words.\r\n2. You are given N space separated strings(i.e. words).\r\n3. You are given a number W representing width of sentence (maxmimum characters a line can hold).\r\n4. You are allowed to append extra spaces only at the end of words.\r\n5. Cost of word-wrap = (e1*e1*e1) + (e2*e2*e2) + (e3*e3*e3) + ....\r\n where e1,e2,e3 ... en are extra-spaces at the end of line 1,line 2,line 3 .... line n(respectively).\r\n (view image to get more clear insight of question).\r\n6. Find the MINIMUM COST of optimal word-wrapping method.\r\n","inputFormat":"A number N (representing \"NUMBER OF WORDS\").\r\nstr1 ,str2 ,str3 ,str4 .... strn (N space separated strings).\r\nA number W (representing \"WIDTH OF LINE\").\r\n","outputFormat":"Find minimum cost of word-wrapping.\r\nCheck the sample output and question video.","constraints":"1 &lt;= N &lt;= 10\r\n1 &lt;= len(str) &lt;= 15\r\nMAXIMUM LENGTH(str) &lt;= W","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.Scanner;\r\n\r\npublic class Main{\r\n // return cost of optimal word-wrap.\r\n private static int wordWrap(String []words,int width){\r\n\r\n // write your code here.\r\n \r\n return 0;\r\n } \r\n \r\n public static void main(String []args){\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n \r\n String words[] = new String[n];\r\n \r\n for(int i = 0 ; i < n ;i++)\r\n words[i] = scn.next();\r\n \r\n int width = scn.nextInt();\r\n \r\n System.out.println(wordWrap(words, width));\r\n\r\n scn.close();\r\n }\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"4\r\naaa bb cc aaaaa\r\n6","sampleOutput":"29\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"0ed79e40-48be-4fe9-88a0-ac7a3d2bf3e8","name":"Word Wrap","slug":"word-wrap","type":1}],"next":{"id":"8d8ab01b-f102-4543-973a-69f3c57119ce","name":"2 Key Keyboard","type":1,"slug":"2-key-keyboard"},"prev":{"id":"39b6079d-b13c-41ed-91d5-598e591c555e","name":"Word Break 2","type":1,"slug":"word-break-2"}}}

Word Wrap

1. You are given a number N representing number of words. 2. You are given N space separated strings(i.e. words). 3. You are given a number W representing width of sentence (maxmimum characters a line can hold). 4. You are allowed to append extra spaces only at the end of words. 5. Cost of word-wrap = (e1*e1*e1) + (e2*e2*e2) + (e3*e3*e3) + .... where e1,e2,e3 ... en are extra-spaces at the end of line 1,line 2,line 3 .... line n(respectively). (view image to get more clear insight of question). 6. Find the MINIMUM COST of optimal word-wrapping method.

{"id":"29284a4a-7f49-47eb-a8f7-6a3a00063a5e","name":"Word Wrap","description":"1. You are given a number N representing number of words.\r\n2. You are given N space separated strings(i.e. words).\r\n3. You are given a number W representing width of sentence (maxmimum characters a line can hold).\r\n4. You are allowed to append extra spaces only at the end of words.\r\n5. Cost of word-wrap = (e1*e1*e1) + (e2*e2*e2) + (e3*e3*e3) + ....\r\n where e1,e2,e3 ... en are extra-spaces at the end of line 1,line 2,line 3 .... line n(respectively).\r\n (view image to get more clear insight of question).\r\n6. Find the MINIMUM COST of optimal word-wrapping method.\r\n","inputFormat":"A number N (representing \"NUMBER OF WORDS\").\r\nstr1 ,str2 ,str3 ,str4 .... strn (N space separated strings).\r\nA number W (representing \"WIDTH OF LINE\").\r\n","outputFormat":"Find minimum cost of word-wrapping.\r\nCheck the sample output and question video.","constraints":"1 &lt;= N &lt;= 10\r\n1 &lt;= len(str) &lt;= 15\r\nMAXIMUM LENGTH(str) &lt;= W","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.Scanner;\r\n\r\npublic class Main{\r\n // return cost of optimal word-wrap.\r\n private static int wordWrap(String []words,int width){\r\n\r\n // write your code here.\r\n \r\n return 0;\r\n } \r\n \r\n public static void main(String []args){\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n \r\n String words[] = new String[n];\r\n \r\n for(int i = 0 ; i < n ;i++)\r\n words[i] = scn.next();\r\n \r\n int width = scn.nextInt();\r\n \r\n System.out.println(wordWrap(words, width));\r\n\r\n scn.close();\r\n }\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"4\r\naaa bb cc aaaaa\r\n6","sampleOutput":"29\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"0ed79e40-48be-4fe9-88a0-ac7a3d2bf3e8","name":"Word Wrap","slug":"word-wrap","type":1}],"next":{"id":"8d8ab01b-f102-4543-973a-69f3c57119ce","name":"2 Key Keyboard","type":1,"slug":"2-key-keyboard"},"prev":{"id":"39b6079d-b13c-41ed-91d5-598e591c555e","name":"Word Break 2","type":1,"slug":"word-break-2"}}}
plane

Editor

Loading...

Word Wrap

medium

1. You are given a number N representing number of words. 2. You are given N space separated strings(i.e. words). 3. You are given a number W representing width of sentence (maxmimum characters a line can hold). 4. You are allowed to append extra spaces only at the end of words. 5. Cost of word-wrap = (e1*e1*e1) + (e2*e2*e2) + (e3*e3*e3) + .... where e1,e2,e3 ... en are extra-spaces at the end of line 1,line 2,line 3 .... line n(respectively). (view image to get more clear insight of question). 6. Find the MINIMUM COST of optimal word-wrapping method.

Constraints

1 <= N <= 10 1 <= len(str) <= 15 MAXIMUM LENGTH(str) <= W

Format

Input

A number N (representing "NUMBER OF WORDS"). str1 ,str2 ,str3 ,str4 .... strn (N space separated strings). A number W (representing "WIDTH OF LINE").

Output

Find minimum cost of word-wrapping. Check the sample output and question video.

Example

Sample Input

4 aaa bb cc aaaaa 6

Sample Output

29

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode