I'm not sure why don't you save player position (and maybe it's animation) for every frame, let's do a little bit calculations: each player position is combined of two floating point numbers (aka. 8 bytes), you also need to know which animation the character was showing at that frame and exactly how much which frame of the animation was shown in that specific time (aka. another 8 bytes). I can't think of anything else, but let's assume we need another 8 bytes for reserve. it means total 24 bytes per snapshot.
Now if you are talking about SMB most runs won't be longer than 5 minutes, meaning 300 seconds or 18k frames (60 fps). If you want to show a replay exactly as shown in the first play, you need to store all those 60 frames per second, based on what we calculated before you'll need 18k * 24bytes memory per try (meaning 432kb). If your target market is PC, you won't have any problems storing even 100 replications (43MB) which is even more than what SMB showed after you've finished level.
Now let's see how can we optimize our data storage system to consume less memory:
- you really don't need 8 bytes of floating point number for position. Usually you can compress all those data into 3 or 4 bytes of fixed point numbers.
- you don't need 8 bytes for animation either, you normally don't have more than 256 different animations for your main character, and non of your animations contain more than 256 different frames, so you can store all the data in 2 bytes at most.
- I've put 8 bytes for reserve, so I will expect you to use those 8 bytes wisely (reduce them as much as you can!)
- you don't need to save replay at 60fps either, you can easily save 20fps and interpolate all the frames between them. I'm pretty sure user won't notice any difference.
- since you are suggesting your game consist of mini-levels I think 5 minutes is really more than a normal run in your game, though I won't reduce that either!
Now let's see how much data we need for this new replay system (4 + 2 + 8) * 20 * 5 * 60 = 84kb per replication, which means you can easily show up to 100 replications in any iOS /Android device!
Do you need to save even more memory? You can try storing only key frames with their time and interpolate all the frames between them. key frames simply mean the frames where player's Velocity changed due to any reason (hitting obstacles, user input change, ...) but it'll result in consuming much more processing power while showing those replays.