We construct BRST operators for certain higher-spin extensions of the Virasoro algebra, in which there is a spin-s gauge field on the world sheet, as well as the spin-2 gauge field corresponding to the two-dimensional metric. We use these BRST operators to study the physical states of the associated string theories, and show how they - related to certain minimal models.