Connection Status:
Competition Arena > SentenceSplitting

SentenceSplitting

SRM 285 · 2006-01-24 · by Andrew_Lazarev

SRM 285 · 2006-01-24 · by Andrew_Lazarev · Brute Force, Simple Search, Iteration
Class Name: SentenceSplitting
Return Type: int
Method Name: split
Arg Types: (string, int)
Problem Statement

Problem Statement

You have a sentence written entirely in a single row. You would like to split it into several rows by replacing some of the spaces with "new row" indicators. Your goal is to minimize the width of the longest row in the resulting text ("new row" indicators do not count towards the width of a row). You may replace at most K spaces.

You will be given a String sentence and an int K. Split the sentence using the procedure described above and return the width of the longest row.

Constraints

  • sentence will contain between 1 and 50 characters, inclusive.
  • sentence will consist of only letters ('a'-'z', 'A'-'Z') and spaces (' ').
  • Each space character in sentence will be between two letters.
  • K will be between 1 and 50, inclusive.
Examples
0)
"This is a test sentence"
1
Returns: 13

You should split the sentence between the words "a" and "test".

1)
"This is another test sentence"
2
Returns: 12

You should split the sentence between the words "is" and "another", and between the words "test" and "sentence".

2)
"TheOnlyWord"
37
Returns: 11
3)
"One veeeeeeeeeeeeeeeeeeery long word"
2
Returns: 22
4)
"HUIUueVIk uDCCrzrNJOje Vw mIkGzM Dla eSYbaLpuIhaC"
4
Returns: 12

Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SentenceSplitting with a public method int split(string sentence, int K) · 113 test cases · 2 s / 256 MB per case

Submitting as anonymous