For some reason I get TLE with G++ 4.9 and AC with Visual C++ 2013 with exactly the same code. I tried to use scanf/printf instead of cin/cout, but had no difference. On my machine this code works <100ms for every n with G++. Can anyone explain why I get TLE with G++? Thanks!

#include <string>
#include <queue>
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    queue<string> result;
    result.push("a");
    result.push("b");
    result.push("c");
    char abc[] = {'a', 'b', 'c'};
    for (int i = 1; i < n; i++) {
        while (true) {
            string &s = result.front();
            if (s.size() > i) {
                break;
            }
            char last = s[s.size() - 1];
            if (s.size() > 1) {
                char lbo = s[s.size() - 2];
                for (int k = 0; k < 3; k++) {
                    char c = abc[k];
                    if (last != c && lbo != c) {
                        result.push(s + c);
                    }
                }
            } else {
                for (int k = 0; k < 3; k++) {
                    char c = abc[k];
                    if (last != c) {
                        result.push(s + c);
                    }
                }
            }
            result.pop();
        }
        if ((i + 1) * result.size() > 100000) {
            cout << "TOO LONG";
            return 0;
        }
    }
    while (!result.empty()) {
        cout << result.front() << endl;
        result.pop();
    }
    return 0;
}

Because s+c is a temporary object
You are creating temporary objects and throwing them away O(N)  times

Looks like G++ failed to notice that it is unnecessary to create and destroy objects

And MSVC noticed that and replaced with something more effective