Determine the longest path from the orignal with missing inputs

Input

You are given a string program which describes the program in its current state. The i-th character in program represents the i-th command that is executed and will be 'L', 'R' or '?' (quotes for clarity). 'L' represents a legible move left, 'R' a legible move right and '?' a command that is illegible so you can choose 'L' or 'R' in its place.
There are multiple input strings. The string’s length is not more than 50.

Output

For each string, you program should output an integer indicates the largest reach a repaired program can have. 

Sample Input

LLLRLRRR
??????

Sample Output

3
6

Solution

If there is no question mark, it's easy to solve.
Assume L meaning step +1 and  R meaning step -1 away from  the orginal.  At each step, the distance between current position to the orignal = the distance between last position to the orignal + (L? 1 : -1)
Scan the input string, for each step i, we can get the value of distance(i, orignal). The problem becomes finding the larget absolute value of the distance.

The problem is we have question mark, which can  be L or R.
We can prove that to maximize the distance, the question mark in one input string should either be all 'L' or all 'R'.
Then we can replace the question mark by 'L' and 'R', then compare the maximum distances obtained from each replacement.

<pre>
int countMaxMove(int *moves, int inputLen, char replace) {
if (inputLen == 0) {
return 0;
}

int movesofar = 0;
int maxmoves = 0;
for (int i = 0; i < inputLen; i++) {
if (moves[i] == 0) {
if (tolower(replace) == 'l')
moves[i] = 1;
else if (tolower(replace) == 'r')
moves[i] = -1;
}

movesofar += moves[i];
if (maxmoves <= abs(movesofar))
maxmoves = abs(movesofar);
}

return maxmoves;
}

int main(int argc, char* argv[]) {
char buf[51];
scanf("%s", buf);
int inputLen = strlen(buf);
if (inputLen > 0) {
int moves[inputLen];
int unknown = 0;
for (int i = 0; i < inputLen; i++) {
char c = buf[i];
if (tolower(c) == 'l') {
moves[i] = 1;
}

if (tolower(c) == 'r') {
moves[i] = -1;
}

if (tolower(c) == '?') {
moves[i] = 0;
unknown += 1;
}

}

int lmoves = 0;
int rmoves = 0;

if (unknown) {

//replace to L
int repair[inputLen];
memcpy(repair, moves, inputLen * sizeof(int));
lmoves = countMaxMove(repair, inputLen, 'L');

//replace to R
memcpy(repair, moves, inputLen * sizeof(int));
rmoves = countMaxMove(repair, inputLen, 'R');
} else {
lmoves = countMaxMove(moves, inputLen, 'L');
}

printf("%d\n", lmoves > rmoves ? lmoves : rmoves);
}

return 0;
}
</pre>