Every class does implement an interface (i.e. contract) insofar as it provides a non-private API. Whether you should choose to represent the interface separately as a Java interface depends on whether the implementation is "a concept that varies".
If you are absolutely certain that there is only one reasonable implementation then there is no need for an interface. Otherwise an interface will allow you to change the implementation without changing client code.
Some people will shout "YAGNI", assuming that you have complete control over changing the code should you discover a new requirement later on. Other people will be justly afraid that they will need to change the unchangeable - a published API.
If you don't implement an interface (and use some kind of factory for object creation) then certain kinds of changes will force you to break the Open-Closed Principle. In some situations this is commercially acceptable, in others it isn't.
Can you describe a situation where it's not a good idea to use interfaces?
In some languages (e.g. C++, C#, but not Java) you can get a performance benefit if your class contains no virtual methods.
In small programs, or applications without published APIs, then you might see a small cost to maintaining separate interfaces.
If you see a significant increase in complexity due to separating interface and implementation then you are probably not using interfaces as contracts. Interfaces reduce complexity. From the consumer's perspective, components become commodities that fulfil the terms of a contract instead of entities that have sophisticated implementation details in their own right.