my solution

bool dp[position_on_the_coordinate_axis][prefix_of_commands_we_did][number_of_changes_we_did][our_direction] — can we stay on "pos" if we did "pref" commands and chamged "num" commands and we look(left, if dir == 0, right if dir == 1)

Consider an easier version of this problem which just requires changing any command at most once or not changing it at all, so you will have to process the string letter by letter. and for each one you decide changing it or not.

for example, if the current command processed = 'F', you have two options: - 1) decide not to change it (which means increasing your current position by 1 in the current direction) - 2) if there are enough changes that haven't been done, decide to change it once (which means changing your direction and decrementing number of changes required) - the same applies if current = 'T', just inverse the logic.

so it is obvious that what we need to remember in the state is the (current command the decisions are applied to), (the current direction), (the position) , (the remaining changes).

• the original problem allows us that if we decided to change any command, we can change it a lot of times, as long as there are remaining changes.

• so when you are deciding to change a command you can change it from (1) to (remaining changes) no. of times, so if(remaining changes > 0) you can loop from (1 -> remaining changes) and for each one get the corresponding character for this change, and apply again the same logic mentioned above, but with decrementing (remaining changes) by the number of changes you used, and in each iteration maximize that sub-problem, lets call that res2. and the result of not changing the command is res1.

• the result for this sub-problem is max(res1,res2)

• the solution 8336867