입력이 한 줄 밖에 안 되므로 stdin.readline을 할 필요는 없습니다. 특히 스트링을 입력받는 상황이면 개행문자때문에 오히려 더러워집니다. 스트링 입력이 몇 만줄이어서 꼭 stdin.readline을 써야 하는 상황이면 stdin.readline().rstrip()이나 [:-1]으로 입력받을 수 있습니다.

s = "a"+s는 절대 하면 안 됩니다. s = s+"a"는 O(1)이 걸리지만, s = "a"+s는 "a"의 끝에 s의 문자를 하나씩 붙여넣기 때문에 O(len(s))가 걸립니다. 10줄에서 이것이 len(bins)번 반복되므로 여기에서 시간초과가 납니다.