Sachverhalt:
A.
Die E._ AG ist Eigentümerin des Grundstücks KTN 77, Seestatt, in Altendorf, auf welchem das ehemalige Gasthaus Adler stand.
Die E._ AG reichte das Baugesuch "Ersatzneubau Mehrfamilienhaus Adler" auf dem Grundstück KTN 77 ein. Dieses Baugesuch wurde im kantonalen Amtsblatt Nr. 27 vom 7. Juli 2017 publiziert und öffentlich aufgelegt. Gegen das Bauvorhaben erhoben neben einer Drittpartei auch A., B., C. und D. A._, Eigentümer der nahe gelegenen Parzelle KTN 75, am 26. Juli 2017 Einsprache.
Im kantonalen Amtsblatt Nr. 32 vom 11. August 2017 wurde ein weiteres Baugesuch "Ersatzneubau Mehrfamilienhaus Adler" publiziert und öffentlich aufgelegt. Die beiden Baugesuche von Juli respektive August 2017 sind inhaltlich identisch; sie unterscheiden sich einzig in Bezug auf die Bauherrschaft. Im Gesuch von Juli 2017 wird die E._ AG als Bauherrschaft angegeben. Im Gesuch von August 2017 wird F._ (Architekt) als Bauherr genannt und die E._ AG als Grundeigentümerin aufgeführt. Gegen dieses zweite Baugesuch erhob die vorerwähnte Drittpartei wiederum Einsprache. A., B., C. und D. A._ reichten hingegen keine Einsprache ein.
Am 16. Oktober 2017 zog die E._ AG ihr Baugesuch vom 7. Juli 2017 (Datum der Publikation) zurück. Mit Beschluss vom 6. November 2017 schrieb der Gemeinderat Altendorf dieses Baugesuch infolge Rückzugs ab.
Mit Gesamtentscheid vom 15. Januar 2018 erteilte das Amt für Raumentwicklung des Kantons Schwyz (ARE/SZ) für das Baugesuch vom 11. August 2017 (Datum der Publikation) die kantonale Baubewilligung unter Auflagen und Nebenbestimmungen. Am 26. Januar 2018 erteilte der Gemeinderat Altendorf die Baubewilligung für den Abbruch des bestehenden Mehrfamilienhauses Adler und die Erstellung eines Ersatzneubaus auf Parzelle KTN 77, unter gleichzeitiger Eröffnung des Gesamtentscheids des ARE/SZ vom 15. Januar 2018. Dieser Beschluss erwuchs unangefochten in Rechtskraft.
B.
Im kantonalen Amtsblatt vom 4. Mai 2018 wurde das Gesuch der E._ AG "Pfählung Mehrfamilienhaus" auf dem Grundstück KTN 77 publiziert und öffentlich aufgelegt. Hiergegen erhoben A., B., C. und D. A._ Einsprache beim Gemeinderat Altendorf. Am 7. Juni 2018 zog die Bauherrschaft ihr Pfählungsgesuch zurück, da weitere Sondierungen und Abklärungen gezeigt hätten, dass auf eine Pfählung verzichtet werden könne.
Am 31. Mai 2018 beantragten A., B., C. und D. A._ beim Gemeinderat Altendorf, die Baubewilligung vom 26. Januar 2018 für den Abbruch des Mehrfamilienhauses Adler sei zu widerrufen. Sie machten geltend, aus den neuen Baugesuchsunterlagen ergebe sich, dass das Neubauprojekt auf eine Pfählung und auf Rühlwände angewiesen sei, was aus gewässerschutzrechtlicher Sicht (Unterschreitung des mittleren Grundwasserspiegels) problematisch sei.
Am 4. Juni 2018 lehnte der Gemeinderat Altendorf das Widerrufsgesuch ab und entzog einer allfälligen Beschwerde die aufschiebende Wirkung.
Hiergegen erhoben A., B., C. und D. A._ am 7. Juni 2018 Beschwerde beim Regierungsrat des Kantons Schwyz. Am 8. Juni 2018 reichten sie überdies eine Aufsichtsbeschwerde ein. Der Regierungsrat wies die Beschwerde mit Beschluss vom 19. Juni 2018 ab und entschied, der Aufsichtsbeschwerde werde keine Folge geleistet.
Gegen diesen Entscheid reichten A., B., C. und D. A._ am 21. Juni 2018 Beschwerde beim Verwaltungsgericht des Kantons Schwyz ein. In der Hauptsache beantragten sie den Widerruf der baurechtlichen Bewilligung vom 26. Januar 2018, mit welchem der Abbruch des Mehrfamilienhauses Adler bewilligt worden sei. Einstweilen sei es der Bauherrschaft zu verbieten, dieses abzubrechen.
Mit Zwischenbescheid vom 22. Juni 2018 ordnete der Einzelrichter am Verwaltungsgericht superprovisorisch ein Abbruchverbot an. Dagegen erhob die E._ AG am 2. Juli 2018 Einsprache. Mit Zwischenbescheid vom 27. Juli 2018 hiess das Verwaltungsgericht die Einsprache gut und hob das einstweilige Abbruch- und Veränderungsverbot auf. Es ging - wie die Vorinstanzen - davon aus, die bewilligte Baute sei ohne Pfählung realisierbar.
Diesen Zwischenentscheid fochten A., B., C. und D. A._ am 3. August 2018 mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht an. Mit Urteil 1C_378/2018 vom 18. September 2018 trat das Bundesgericht auf die Beschwerde nicht ein.
Mit Entscheid vom 6. Dezember 2018 wies das Verwaltungsgericht die Beschwerde von A., B., C. und D. A._ vom 21. Juni 2018im Sinne der Erwägungen ab, soweit es darauf eintrat.
C.
Mit Eingabe vom 17. Januar 2019 führen A., B., C. und D. A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Sie beantragen in der Hauptsache die Aufhebung des angefochtenen Entscheids des Verwaltungsgerichts.
Die Vorinstanz, der Regierungsrat und das ARE/SZ verzichten auf Vernehmlassungen. Die Gemeinde Altendorf und die Beschwerdegegnerin beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei.
Die Beschwerdeführer und die Beschwerdegegnerin halten in weiteren Eingaben an ihrem Standpunkt und an ihren Anträgen fest.

Erwägungen:
1.
1.1. Die Beschwerde richtet sich gegen einen kantonal letztinstanzlichen Endentscheid im Bereich des Baurechts, gegen den grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht offen steht (vgl. <ref-law>).
1.2. Gemäss <ref-law> ist zur Beschwerde legitimiert, wer vor der Vorinstanz am Verfahren teilgenommen oder keine Möglichkeit dazu erhalten hat (lit. a), durch den angefochtenen Entscheid besonders berührt ist (lit. b) und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung hat (lit. c). Das erforderliche schutzwürdige Interesse muss nicht nur bei der Beschwerdeeinreichung, sondern auch noch im Zeitpunkt der Urteilsfällung aktuell und praktisch sein. Fällt es im Laufe des Verfahrens dahin, wird die Sache als erledigt erklärt; fehlte es schon bei der Beschwerdeeinreichung, ist auf die Eingabe nicht einzutreten. Das Bundesgericht verzichtet indes ausnahmsweise auf das Erfordernis des aktuellen praktischen Interesses, wenn sich die aufgeworfenen Fragen unter gleichen oder ähnlichen Umständen jederzeit wieder stellen können, eine rechtzeitige Überprüfung im Einzelfall kaum je möglich wäre und die Beantwortung wegen deren grundsätzlicher Bedeutung im öffentlichen Interesse liegt (<ref-ruling> E. 1.3.1 S. 24 f. mit zahlreichen Hinweisen).
1.3.
1.3.1. Die Beschwerdeführer bringen vor, das bisherige Gebäude aus dem 18. Jahrhundert sei mittlerweile abgebrochen und an dessen Stelle sei ein Neubau getreten. Ihnen sei bewusst, dass sie mit ihrer Beschwerde nicht erreichen könnten, dass der Neubau zurückgebaut und das historische Gebäude rekonstruiert werde. Sie müssten sich daher den Einwand gefallen lassen, über kein schutzwürdiges Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids zu verfügen. Die Frage des schutzwürdigen Interesses könne jedoch offen bleiben, da sich insbesondere die Frage nach der Zulässigkeit der gestaffelten Publikation identischer Baugesuche jederzeit und unter gleichen oder ähnlichen Umständen wieder stellen könnte, an ihrer Beantwortung wegen ihrer grundsätzlichen Bedeutung ein hinreichendes öffentliches Interesse bestehe (grosse Relevanz für Bauherren und Einsprechende) und eine rechtzeitige gerichtliche Überprüfung im Einzelfall kaum je möglich wäre (Bauvorhaben vollendet vor abschliessender gerichtlicher Überprüfung).
1.3.2. Die Beschwerdeführer machen weiter geltend, selbst wenn diese aufgeführten Voraussetzungen (E. 1.3.1 hiervor) nicht gegeben sein sollten, sei auf die Beschwerde insoweit einzutreten, als sie die Verletzung von Verfahrensvorschriften bzw. Parteirechten rügten, deren Missachtung eine formelle Rechtsverweigerung darstelle (<ref-ruling> E. 1.3.2 S. 253; <ref-ruling> E. 2.3 S. 301). Konkret sei ihr Anspruch auf rechtliches Gehör gemäss <ref-law> missachtet worden, indem der Gemeinderat Altendorf zwei identische Baugesuche ohne schützenswertes Interesse der Bauherrschaft im kantonalen Amtsblatt habe publizieren lassen.
1.4. Mit ihren Ausführungen räumen die Beschwerdeführer zu Recht ein, dass das Erfordernis des aktuellen praktischen Interesses schon bei Beschwerdeeinreichung fehlte. Umstritten ist, ob ausnahmsweise auf dieses Erfordernis verzichtet werden kann.
Vorliegend geht es um den Spezialfall eines Wiedererwägungsgesuchs nach kantonalem Verwaltungsrechtspflegegesetz. Die Beschwerdeführer beantragen den Widerruf der Baubewilligung vom 26. Januar 2018. Sie hätten das Verfahren um Wiedererwägung vermeiden können, indem sie nicht nur gegen das erste, sondern auch gegen das zweite, ordentlich publizierte Baugesuch fristgerecht Einsprache erhoben hätten, wie dies auch eine Drittpartei getan hat (vgl. Sachverhalt lit. A. hiervor). Im Normalfall ist eine rechtzeitige Überprüfung der von den Beschwerdeführern (in der ersten Einsprache) gegen das Bauvorhaben vorgebrachten Punkte damit durchaus möglich. Auch bei der von den Beschwerdeführern nun aufgeworfenen Frage der Zulässigkeit der gestaffelten Publikation inhaltlich gleichlautender Baugesuche handelt es sich nicht um eine Grundsatzfrage, die sich jederzeit wieder stellen könnte und an deren Beantwortung ein hinreichendes öffentliches Interesse besteht. Eine grosse Bedeutung für Bauherren und Einsprechende kommt der Frage mangels grosser praktischer Relevanz ebenfalls nicht zu. Die Voraussetzungen für einen ausnahmsweisen Verzicht auf das Erfordernis des aktuellen praktischen Interesses sind damit nicht erfüllt.
1.5. Fehlt es den Beschwerdeführern an einem aktuellen praktischen Interesse in der Hauptfrage, so gilt dies auch für die damit eng zusammenhängende prozessuale Frage, ob ihnen insoweit das Recht verweigert wurde. Die Rechtsverweigerungsbeschwerde verfügt insofern über keinen eigenständigen Charakter. Die Rechtslage ist auch nicht vergleichbar mit dem Fall, in dem es den Beschwerdeführern an der Legitimation in der Sache fehlt, Rechtsverweigerungsbeschwerden aber dennoch zulässig sind, soweit sie nicht auf eine inhaltliche Prüfung der Streitsache hinauslaufen (sog. "Star-Praxis", vgl. <ref-ruling> E. 3.2 S. 436 f.). Im Unterschied dazu geht es hier nicht um die Legitimation in der Sache; es mangelt vielmehr an der Aktualität des erforderlichen schutzwürdigen Interesses (siehe zum Ganzen Urteil 1C_605/2014 vom 6. Juli 2015 E. 2.6).
2.
Nach dem Gesagten ist auf die Beschwerde nicht einzutreten.
Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kostenpflichtig (Art. 66 Abs. 1 und 5 BGG). Sie haben der obsiegenden Beschwerdegegnerin eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1, 2 und 4 BGG). Der Gemeinde Altendorf ist keine Parteientschädigung zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Auf die Beschwerde wird nicht eingetreten.
2.
Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern auferlegt.
3.
Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, dem Gemeinderat Altendorf, dem Amt für Raumentwicklung des Kantons Schwyz, dem Regierungsrat des Kantons Schwyz und dem Verwaltungsgericht des Kantons Schwyz, Kammer III, schriftlich mitgeteilt.
Lausanne, 21. Mai 2019
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Der Gerichtsschreiber: Stohner