The most conceptual explanation uses composition of species.
Recall that your Stirling number of the first kind counts collections of $k$ cycles that together contain $n$ points.
Now, you first determine the exponential generating function for cycles:
There are $(n-1)!$ cycles of length $n$, for example, because you regard the list of elements coming after 1 in the cycle.
So, you get $Cycles(z)=\sum_n \frac{(n-1)!}{n!}z^n= \sum \frac{z^n}{n}= \log(\frac 1 {1-z})$.
Then, you determine the exponential generating function for sets of size $k$.
There is only one possibility to do so and it has size $k$:
$Sets_k(z)=\frac{z^k}{k!}$
And, now the miracle occurs:
You want to count $k$-sets of cycles and you find the exponential generating function by calculating $Sets_k$ of $Cycles$ with composition of functions.
So, you get $Sets_k(Cycles(z))= \frac{(\log(\frac 1 {1-z}))^k}{k!}$.
You can read more on this on the corresponding Wikipedia page
or you can read much more on this in the book Combinatorial Species and Tree-Like Structures by F. Bergeron, Gilbert Labelle, Pierre LeRoux.
The generating function for the first set is
$$(x)({1\over 1-x})(x)({1\over 1-x}) = {x^2\over (1-x)^2}$$
The generating function for the second set is
$$(x)({1\over 1-x^2})(x)({1\over 1-x^2})={x^2\over (1-x^2)^2}$$
Since the generating function's coefficient represent the number of element of that length in the set, the difference of the coefficients is basically the number of elements in the difference of the two sets.
Therefore the generating function is
$${x^2\over (1-x)^2} - {x^2\over (1-x^2)^2}={2x^3+x^4\over (1-x^2)^2}$$
Best Answer
Let $f(n)$ be the number of such strings of size $n$. Then the (ordinary) generating function associated with this sequence is $$F(x):=\sum\limits_{n \geq 0} f(n) x^n. $$ Based on your description, $f(n) = 1$ if $n$ is even and $f(n) = 0$ if $n$ is odd. The generating function is $$F(x) = \sum\limits_{n \geq 0}f(n) x^n = 1 + x^2 + x^4 + \cdots = \frac{1}{1 - x^2}.$$
Additionally, if we want the generating function for the number of such strings of size at most $n$, then we have $$\sum\limits_{n \geq 0 } \left(\sum\limits_{k = 0}^n f(k)\right) x^n = \frac{F(x)}{1 - x} = \frac{1}{(1 - x^2)(1 - x)}.$$