The LSP is about the contract of a class, and that inherited classes must still fulfill the same contract as their base class. An interface just in code will typically only define parts of that contract, mainly the syntactical part, and the semantics as far as it ismight be partially given by descriptive names of the methods or the parameters. Other parts of the contract are often just defined in comments, by adding "assertion statements", by making use of specific language features, or they might be encoded into unit tests.
Thus if you solved the LSP violation really, depends on the full semantic contract of your interface. If the contract looks like this (which is IMHO the more obvious behaviour):
// contract: a four sided shape is an object with two individual, independent // properties "width" and "height" interface AFourSidedShape{ public function setWidth($width); public function setHeight($height); public function getWidth(); public function getHeight(); } then Square class does not fulfill the same contract as its base class, so it still violates the LSP. One could write that more formally in terms of "post conditions", checking that each time you call setHeight, the value of getWidth does not change, and vice versa.
If, however, your semantic contract looks like this:
// contract: a four sided shape is an object with two // properties "width" and "height" which must not // be assumed to be independent; maybe changing one can change the other interface AFourSidedShape{ // ... } then there is no LSP violation any more. From your question and the way you describe the constructor constraints, I guess that is the contract you have in mind. However, the latter might violate the principle of least astonishment, a "setter" which for some objects changes another value, and for others it does not, can be mind-boggling to the average user of your class. Better avoid to put such setters in the common interface, LSP obeyed or not.
Side note: of course, the original Square/Rectangle problem can be understood as "is there an implementation where Square derives from Rectangle or vice versa directly which does not violate the LSP". If one reads it this way, then @ScantRoger is correct and your design solves a different problem. However, I read the problem quite differently as is there a way to incorporate inheritance to deal with rectangles and squares in a generic manner without violating LSP, and for this problem the answer is "yes, your suggestion will solve that problem".