We don't need to build string, just set up the string length counter to get the first on bigger than the Number n. Then decompose the F(n)= F(n-1) + F(n-2). This structure indicate the string is always prefix with F(n-1). If number is bigger then F(n-1), then decompose the F(n-2), otherwise decompose F(n-1). This is my Java Version which pass all test:

static int getResult(String one, String two, BigInteger n) {
    List<BigInteger> fcount = new ArrayList<BigInteger>();
    BigInteger oneInt = BigInteger.valueOf(one.length());
    BigInteger twoInt = BigInteger.valueOf(two.length());
    fcount.add(oneInt);
    fcount.add(twoInt);
    int result = -1;
    do{
        fcount.add(oneInt.add(twoInt));
        oneInt = twoInt;
        twoInt = fcount.get(fcount.size()-1);
    }while(twoInt.compareTo(n)<0);
    int i = fcount.size() -3;
    int currentIndex = i;
    while(i>=0) {
        BigInteger current = fcount.get(i);
        if(n.compareTo(current)>0) {
            n = n.subtract(current);
            i--;
            currentIndex = i;
        }
        else
        {
            if(i==0)
                result = one.charAt(n.intValue() - 1);
            if(i==1) 
                result = two.charAt(n.intValue() - 1);
            i = currentIndex - 2;
            currentIndex = i;
        }
    }
    if(result == -1)
        result = two.charAt(n.intValue() - 1);
    return (result - 48);
}