We present the discovery of 1568 RR Lyrae stars in three of the most luminous M31 satellites: And VII (573), NGC 147 (177), and NGC 185 (818). We use their properties to study the formation history of Local Group spiral haloes, and in particular, to infer about the nature of their possible building blocks by comparison with available data for RR Lyrae stars in the halo and in a sample of satellites of M31 and the Milky Way. We find that the brightest satellites and the halos of both galaxies host a number of High Amplitude Short Period (HASP) RR Lyrae variable stars, which are missing in the faintest satellites. HASP variable stars have been shown by Fiorentino et al. to be tracers of a population of stars as metal-rich as [Fe/H] ≃ ‑1.5 and older than ≃ 10 {Gyr}. This suggests that the metal-rich M31 and MW halo component, which manifests through the HASP phenomenon, comes from massive dwarf galaxy building blocks, as the low-mass dwarfs did not chemically enrich fast enough to produce them. All detected variable stars are new discoveries; in particular, this work presents the first detections of RR Lyrae stars in And VII. Moreover, a number of candidate Anomalous Cepheids, and binary and long-period variable stars have been detected. We provide pulsation properties (period, amplitude, mean magnitude), light curves, and time series photometry for all of the variable stars in the three galaxies. Based on observations made with the NASA/ESA Hubble Space Telescope, obtained at the Space Telescope Science Institute, which is operated by the Association of Universities for Research in Astronomy, Inc., under NASA contract NAS 5-26555. These observations are associated with programs #10430 and #11724.