I recently watched this YouTube video (link: https://youtu.be/iXKvwPjCGnY) that talks about colour spaces. Interested I looked it up. Turns out different colour spaces can represent different "subsets" of the visible spectrum. Not all of these subsets are the same size. What I don't understand is how this is achieved. As long as the same number of bytes are used to represent each pixel there are only so many permutations regardless of encoding. Therefore a fixed number of distinct colors. Now I do not understand color spaces. Maybe they do use different numbers of bytes. I tried looking it up but most articles were too obscure and jargony especially Wikipedia. Maybe someone can help me out here?
You are confusing gamut and bit depth. Gamut represents the range of color that can be represented by a color-space. Bit depth represents the precision with which you can define a color within a gamut.
So, if gamut was analogous to the size of a display, bit depth would correspond to the resolution of that display. You can have small displays with very high resolution and inversely, they are not dependent upon one an other. This also means that a color-space with a bigger gamut, for the same bit depth, will display colors that look further apart than if they were in a smaller gamut.
You can see this effect in the following images from the Wikipedia page for color depth (synonym of bit depth) though, here, the gamut (sRGB color gamut) stays constant but the bit depth gets lower:
24-bit color depth vs 4-bit color depth
You can see the colors in the 4-bit variant are as colorful but there are a lot less of them that can be represented compared to the 24-bit variant.
Gamut, if viewed on a 2D surface, represents the area and bit depth represents how many colors are in this area. The more colors there are the smaller the distance between two colors but it's also worth noting that those distances don't need to be linear, you can have higher densities in different places depending on the color space specifications. sRGB, for example, is gamma compressed and so has a higher density of represented colors closer to black than to white.
Also, you said
[...] different colour spaces can represent different "subsets" of the visible spectrum.
which isn't really correct. There is nothing stopping a color-space from defining colors that fall outside of the set of colors we can see. In the CIELAB color-space, for example, it is possible to get a color that would be extremely red, redder than you could see, while at the same time having no lightness whatsoever.
