Matches A but not B in Java Regex?

I have a big document. Lets scale it to

location=State-City-House
location=City-House

So What I want to do is replace all those not starting with State, with some other string. Say "NY". But those starting with State must remain untouched.

So my end result would be

location=State-City-House
location=NY-City-House

1.Obviously I cant use String.replaceAll().

2.Using Pattern.matcher() is tricky since we are using two different patterns where one must be found and one must not be found.

3.Tried a dirty way of replacing "location=State" first with "bocation=State" then replacing the others and then re-replacing.

So, A neat and simple way to do it?