The first solution doesn't work, e.g. when the problem is at the beginning of a line.

The negative look-behind does, but character classes don't belong in the replacement string- you can just type the space:

s/(?<!<)p\sclass=/<p class=/;
[download]