Solution Notes: For each character in our input string, there are two possible "typo" characters to try, giving us potentially 2N different sets of directions to check if our input has length N. To check these quickly, we first scan over our string backwards and compute, for each index i, the relative offset we will reach if we carry out just the "suffix" of instructions i..N. This takes O(N) time. Scanning forward and keeping a running offset of our position and direction relative to the origin, it is now easy to check each index i: the effect of a typo at i is given by our running position/direction up to index i-1, plus the typo command at index i, plus the relative offset of the suffix starting at i+1. We can therefore check all the typo strings in only O(N) time. Each one generates a potential ending point, after which we sort all of these and scan through to count unique entries in the list.

#include <stdio.h>
#include <string.h>
#define MAX_N 100000

typedef struct {
  int x, y;
} Point;

char S[MAX_N+1];
Point P[MAX_N*2], offset[MAX_N+1];

/*            N   E   S   W */     
int Dx[4] = { 0, +1,  0, -1};
int Dy[4] = { +1, 0, -1,  0};

int right_turn(int dir) { return (dir+1)%4; }
int left_turn(int dir)  { return (dir+3)%4; }
int rotate_x(int dir, Point p) {
  if (dir==0) return p.x;
  if (dir==1) return p.y;
  if (dir==2) return -p.x;
  if (dir==3) return -p.y;
}
int rotate_y(int dir, Point p) {
  if (dir==0) return p.y;
  if (dir==1) return -p.x;
  if (dir==2) return -p.y;
  if (dir==3) return p.x;
}

/* Sort by x, breaking ties by y */
static int pcomp(const void *p1, const void *p2)
{
  Point *q1 = (Point *)p1;
  Point *q2 = (Point *)p2;
  if (q1->x == q2->x)
    return q1->y - q2->y;
  return q1->x - q2->x;
}

int main(void)
{
  int i, L, total=0, x=0, y=0, dir=0, n=0;

  freopen ("wrongdir.in", "r", stdin);
  freopen ("wrongdir.out", "w", stdout);

  scanf ("%s", S);
  L = strlen(S);

  /* Compute action of every "suffix" of S */
  for (i=L-1; i>=0; i--) {
    if (S[i]=='F') { offset[i].x = offset[i+1].x;  offset[i].y = 1 + offset[i+1].y; }
    if (S[i]=='L') { offset[i].x = -offset[i+1].y; offset[i].y = offset[i+1].x; }
    if (S[i]=='R') { offset[i].x = offset[i+1].y;  offset[i].y = -offset[i+1].x; }
  }
  
  /* Build a list of all possible destination points */
  for (i=0; i<L; i++) {
    if (S[i]!='F') { 
      P[n].x = x + Dx[dir] + rotate_x(dir, offset[i+1]);
      P[n].y = y + Dy[dir] + rotate_y(dir, offset[i+1]);
      n++;
    }
    if (S[i]!='L') { 
      P[n].x = x + rotate_x(left_turn(dir), offset[i+1]);
      P[n].y = y + rotate_y(left_turn(dir), offset[i+1]);
      n++;
    }
    if (S[i]!='R') { 
      P[n].x = x + rotate_x(right_turn(dir), offset[i+1]);
      P[n].y = y + rotate_y(right_turn(dir), offset[i+1]);
      n++;
    }	
    if (S[i]=='F') { x += Dx[dir]; y += Dy[dir]; }
    if (S[i]=='L') { dir = left_turn(dir); }
    if (S[i]=='R') { dir = right_turn(dir); }
  }

  /* Sort and count unique points */
  qsort (P, 2*L, sizeof(Point), pcomp);

  for (i=0; i<2*L; i++)
    if (i==0 || P[i].x!=P[i-1].x || P[i].y!=P[i-1].y) total++;

  printf ("%d\n", total);
  
  return 0;
}