Being constrained to 4 frames will make it difficult, but I think the walk-cycle would still benefit from not having the idle pose incorporated into it.
I used
this ubiquitous 8 frame walk-cycle (first Google result), & reduced it to 4 frames by excluding half the frames, either odd or even.
odds / evens
As this illustrates, although the legs do overlap each other in the odds animation, one leg is prominently bent.