Android: I lost my android key store, what should I do?

No, there is no chance to do that. You just learned how important a backup can be.

You can create a new keystore, but the Android Market wont allow you to upload the apk as an update - worse still, if you try uploading the apk as a new app it will not allow it either as it knows there is a 'different' version of the same apk already in the market even if you delete your previous version from the market

Do your absolute best to find that keystore!!

When you find it, email it to yourself so you have a copy on your gmail that you can go and get in the case you loose it from your hard drive!

Brute Force is the only way!

Here is a script that helped me out:

https://code.google.com/p/android-keystore-password-recover/wiki/HowTo

Using a list of 5-10 possible words from memory, it recovered my password in <1 sec.