Have some marking on the text box on the submission page to give a clue about where the 80 character limit is.
Or just chop titles at 80 chars.
I would find it easier to trim down characters and make replacements if I had a guide. Without the guide it is tempting to remove whole words and sometimes that becomes misleading or link baity.