제가 푼 방식 설명드리겠습니다.
일단 -1 나올때는 따로 처리하구요.

앞으로 끼워넣는다는 성질을 중요하게 생각해서 접근을 하면
뒤에서 부터 확인을 해서 약간의 투포인터를 섞어서 어디까지 가는지를 생각하면 됩니다.
ㅠ 제가 설명을 개못했는데
예시를 들어보면

ABC
CBA
ABC를 살펴보는데 맨 뒤 글자는 C. C를 매칭할때까지 아래 문자열을 살펴봅니다. 그런데 CBA의 뒤에서 부터 처음으로 C가 나오는 index는 0이니까 
0으로 위치를 옮겨주면 더 살펴볼게 없으므로 매칭이 끝납니다. 그럼 남은건 A,B 2개니까 2 출력 이런식으로 했습니다.

적당히 남은것들의 순서를 옮겨줌으로써 최적의 경우로 이동시키면 그렇게 됩니다..