Maximize the number of lines that end in a certain character

Question

You are given a line of strings, each words are seperated by spaces. You can only insert new lines in the 5-10th column of your string. Your goal is to maximize the number of lines that end with the character x. How would you do this for example.

Edit: The words can end with any character, Say you are given the text

abcdfg cdx abcdx abcdefg aa ggffx ax

then the way to display them would be

column:
1234567890
abcdfg cdx
abcdx
abcdefg 
aa ggfx
ax

this would maximize the result because it has 4 lines that end with x

I feel the real problem of this question is how do we brake if it doesn't end with x and it is at a position that can brake.

Observe

abcdefg 
aa ggfx
ax

If aa was on the 1st line with abcdefg then we will only be able to have 1 more line of x because ggfx can't brake right away. As a result ggfx ax would be on the same line

Answer 1

I would naively try something like the following pseudocode:

string foo = "abcdfg cdx abcdx ggx"; 
string newFoo = foo; /* Assumes immutable strings */

int startIndex = 5; 
int endIndex = 10; 
int inserts = 0;

for (int i=startIndex-1; i<=endIndex-1 && i<foo.Length-1; i++) 
{ 
 if (foo.Substring(i, 1) == "x") /* Substr is (startIn, length) */ 
 { 
    newFoo = newFoo.Insert(i+1+inserts, "\n");
    inserts++;
 } 
} 

Will leave starting spaces if next char was a space on the break. Not sure if this is desired.

Answer 2

Break the line every time you can break the line and encounter the appropriate character. If there is no target character within the next nine, break all the time.

This will give an optimal answer, unfortunately. It's a simple game.

It would be more interesting if we could score for lines that had the target character in some range of columns (say, in columns 8-10). But with only the last column counting, greedy wins the day.

I'm assuming here you are allowed to chop words up without having to hyphenate or anything. But you didn't give us other rules, so what other assumption could I make?

String str = "000x0dfkdfjfxxiwrhx fsjhfx fwuhxjhfe xj etc etc you get it";
int doneidx = 0;
char targetchar = 'x';
StringBuffer tmp = new StringBuffer();
while (doneidx < str.length()) {
    if (tmp.length() < 5) {
        tmp.append(str.charAt(doneidx));
    } else {
        for (int i = 0; i < 6; i++) {
            if (doneidx+i < str.length() && str.charAt(doneidx+i) == targetchar) {
                tmp.append(str.substring(doneidx, doneidx+i+1)); 
                doneidx += i+1;
                break;
            }
        }
        System.out.println(tmp.toString());
        tmp = new StringBuffer();
    }
}

This is an O(N^2) algorithm. It could be reduced to O(N) using memoization. But, honestly, I don't think it matters here.