Sachverhalt:
A.
A.a. Das Obergericht des Kantons Solothurn erklärte A._ am 14. April 2010 zweitinstanzlich der Vergewaltigung und der sexuellen Handlungen mit einem Kind schuldig. Es verurteilte ihn dafür sowie in Berücksichtigung des erstinstanzlich in Rechtskraft erwachsenen Schuldspruchs wegen mehrfacher Übertretung des Betäubungsmittelgesetzes zu einer Freiheitsstrafe von fünf Jahren. Es ordnete eine stationäre therapeutische Massnahme gemäss <ref-law> an und schob den Vollzug der Freiheitsstrafe zugunsten der Massnahme auf. Die von A._ gegen die Massnahme nach <ref-law> erhobene Beschwerde in Strafsachen wies das Bundesgericht ab (Urteil 6B_710/2010 vom 25. November 2010).
A.b. Das Amtsgericht von Olten-Gösgen verlängerte die stationäre Massnahme am 14. Januar 2016 auf Antrag des Departements des Inneren des Kantons Solothurn, Amt für Justizvollzug (nachfolgend: DdI/SO), um fünf Jahre. Die Beschwerdekammer des Obergerichts des Kantons Solothurn hob am 16. September 2016 den Entscheid des Amtsgerichts auf und verlängerte die Massnahme nicht. Stattdessen ordnete es eine ambulante Behandlung verbunden mit Bewährungshilfe an, wobei es den stationären Massnahmenvollzug zur Einleitung der ambulanten Behandlung einstweilen aufrechterhielt. Den Antrag von A._ auf umgehende Entlassung aus dem Straf- und Massnahmevollzug wies es in diesem Sinne ab. Die Entschädiungsforderung von A._ für unrechtmässige Haft seit dem 23. August 2011 wies es ebenfalls ab. Das Bundesgericht hiess die von A._ dagegen erhobene Beschwerde in Strafsachen im Entschädigungspunkt gut (vgl. Urteil 6B_1213/2016 vom 8. März 2017).
A.c. Mit Verfügung vom 13. Oktober 2016 hob das DdI/SO die mit Urteil des Obergerichts des Kantons Solothurn vom 14. April 2010 angeordnete stationäre Massnahme nach <ref-law> zufolge Aussichtslosigkeit rückwirkend per 14. Dezember 2014 auf und beantragte beim Amtsgericht von Olten-Gösgen die Verwahrung von A._ gemäss Art. 64 i.V.m. <ref-law>.
B.
B.a. Am 20. November 2018 eröffnete die Staatsanwaltschaft des Kantons Solothurn gegen A._ eine Untersuchung wegen des Verdachts auf sexuelle Handlungen mit einem Kind. In der Folge dehnte die Staatsanwaltschaft die Untersuchung auf weitere Vorwürfe aus.
B.b. Am 4. Dezember 2018 hob das DdI/SO die von der Beschwerdekammer des Obergerichts des Kantons Solothurn am 16. September 2016 angeordnete ambulante Massnahme nach <ref-law> wegen Aussichtslosigkeit mit sofortiger Wirkung auf und beantragte beim Amtsgericht von Olten-Gösgen die Verwahrung von A._.
B.c. Am 17. Dezember 2019 erhob die Staatsanwaltschaft Solothurn beim Amtsgericht von Olten-Gösgen Anklage gegen A._ wegen mehrfacher sexueller Handlungen mit Kindern, sexueller Nötigung, mehrfacher Schändung, mehrfacher harter Pornografie und mehrfacher sexueller Belästigung. Die Staatsanwaltschaft beantragte in der Anklageschrift, das Hauptverfahren sei mit den hängigen Nachverfahren gegen A._ bezüglich Anordnung der Verwahrung zu vereinigen.
B.d. Mit Beschluss vom 4. Juni 2020 vereinigte das Amtsgericht von Olten-Gösgen das Hauptverfahren betreffend die Anklage der Staatsanwaltschaft Solothurn vom 17. Dezember 2019 (Verfahren OGSAG.2019.28) mit dem (sistierten) Nachverfahren auf Anordnung der Verwahrung gemäss Antrag vom 13. Oktober 2016 (Verfahren OGSAG.2016.34). Das Obergericht des Kantons Solothurn wies die Beschwerde von A._ gegen die Verfahrensvereinigung am 8. Juli 2020 ab. Das Bundesgericht trat auf die von A._ dagegen erhobene Beschwerde in Strafsachen am 2. September 2020 nicht ein (Urteil 1B_436/2020 vom 2. September 2020).
B.e. Das Amtsgericht von Olten-Gösgen sprach A._ mit Urteil vom 10. Dezember 2020 der mehrfachen sexuellen Handlung mit Kindern, der mehrfachen Schändung, der mehrfachen Pornografie und der sexuellen Belästigung schuldig (Anklageschrift Ziff. 1.2, 1.3, 4.2, 4.3, 5 und 6.2). Von den Vorwürfen der mehrfachen sexuellen Handlungen mit Kindern, der sexuellen Nötigung, der Schändung und der sexuellen Belästigung gemäss den Anklageziffern 1.1, 2.1, 2.2, 3, 4.1 und 6.1 sprach es ihn frei. Es verurteilte A._ zu einer Freiheitsstrafe von 30 Monaten, einer bedingten Geldstrafe von 10 Tagessätzen zu Fr. 10.-- und einer Busse von Fr. 200.--. Die mit Entscheid der Beschwerdekammer des Obergerichts des Kantons Solothurn vom 16. September 2016 angeordnete ambulante Massnahme nach <ref-law> hob es auf. Den Antrag auf Verwahrung von A._ wies es ab. Es verbot A._ jedoch lebenslänglich jede berufliche und jede organisierte ausserberufliche Tätigkeit, die einen regelmässigen Kontakt zu Minderjährigen umfasst. Zudem auferlegte es diesem für die Dauer von fünf Jahren ein Kontaktverbot sowie ein Rayonverbot und ordnete Bewährungshilfe an. Weiter stellte es im vom DdI/SO am 13. Oktober 2016 eingeleiteten Nachverfahren betreffend nachträgliche Verwahrung eine Verletzung des Beschleunigungsgebots fest, wofür es A._ eine Genugtuung von Fr. 2'000.-- zzgl. Zins von 5% seit dem 31. Oktober 2017 zusprach.
B.f. Gegen das Urteil des Amtsgerichts von Olten-Gösgen vom 10. Dezember 2020 gelangten u.a. die Staatsanwaltschaft und A._ mit Berufung an die Strafkammer des Obergerichts des Kantons Solothurn.
B.g. Die Staatsanwaltschaft erhob am 25. Januar 2021 zudem bei der Beschwerdekammer des Obergerichts des Kantons Solothurn Beschwerde mit den Anträgen, Dispositiv-Ziff. 6 (Abweisung der Anträge auf Verwahrung), 17 und 18 (Verletzung des Beschleunigungsgebots und Ausrichtung einer Genugtuung an A._) sowie 22-24 (Kostenfolgen) des Urteils des Amtsgerichts von Olten-Gösgen vom 10. Dezember 2020 seien aufzuheben und gegenüber A._ sei gestützt auf die Anträge des DdI/SO vom 13. Oktober 2016 resp. 4. Dezember 2018 die nachträgliche Verwahrung anzuordnen, eventualiter zunächst eine stationäre Massnahme nach <ref-law>. Zudem sei festzustellen, dass das Beschleunigungsgebot nicht verletzt wurde, und es sei A._ keine Genugtuung auszurichten.
B.h. Die Strafkammer des Obergerichts des Kantons Solothurn gab den Parteien im hängigen Berufungsverfahren gegen das Urteil des Amtsgerichts von Olten-Gösgen vom 10. Dezember 2020 mit Verfügung vom 3. Februar 2021 Gelegenheit, sich zur sachlichen Zuständigkeit des Berufungsgerichts zur Überprüfung des Urteils vom 10. Dezember 2020 zu äussern. Mit Beschluss vom 18. März 2021 entschied die Strafkammer des Obergerichts, sie sei für eine umfassende Prüfung des erstinstanzlichen Urteils und insbesondere auch der Frage der Verwahrung, zuständig. Die Beschwerdekammer des Obergerichts des Kantons Solothurn schrieb daraufhin das bei ihr hängige Beschwerdeverfahren mit Beschluss vom 30. März 2021 als gegenstandslos ab.
C.
Die Staatsanwaltschaft des Kantons Solothurn gelangt gegen den Beschluss der Beschwerdekammer des Obergerichts des Kantons Solothurn vom 30. März 2021 mit Beschwerde in Strafsachen an das Bundesgericht. Sie beantragt, der angefochtene Beschluss sei aufzuheben und die Streitsache sei zur Neubeurteilung an die Vorinstanz zurückzuweisen.
D.
A._ beantragt mit Beschwerde in Strafsachen, der Beschluss der Strafkammer des Obergerichts des Kantons Solothurn vom 18. März 2021 sei aufzuheben und es sei festzustellen, dass die Strafkammer des Obergerichts des Kantons Solothurn nur für die Überprüfung der Abweisung des Antrags der Staatsanwaltschaft auf Verwahrung, nicht jedoch für die Überprüfung der Abweisung der Anträge des DdI/SO auf nachträgliche Verwahrung zuständig sei. A._ ersucht um unentgeltliche Rechtspflege.

Erwägungen:
1.
Das Bundesgericht vereinigt mehrere Verfahren, wenn sie in einem engen sachlichen Zusammenhang stehen, namentlich wenn sie sich gegen denselben Entscheid richten und die gleichen Parteien oder ähnliche Rechtsfragen betreffen (vgl. <ref-law> i.V.m. <ref-law>; <ref-ruling> E. 1; <ref-ruling> E. 1; <ref-ruling> E. 1). Dies ist vorliegend der Fall, da es in beiden Beschwerden um die sachliche Zuständigkeit (Beschwerdekammer oder Strafkammer des Obergerichts des Kantons Solothurn) bzw. die Frage nach dem Rechtsmittel (Beschwerde oder Berufung) für die Überprüfung des Urteils des Amtsgerichts von Olten-Gösgen vom 10. Dezember 2020 geht. Es rechtfertigt sich daher, die beiden Verfahren zu vereinigen und die Beschwerden in einem einzigen Entscheid zu behandeln.
2.
2.1. Die Beschwerdeführerin 1 ficht den Entscheid vom 30. März 2021 an. Bei diesem handelt es sich um einen Endentscheid, welcher das bei der Beschwerdekammer des Obergerichts des Kantons Solothurn hängige Beschwerdeverfahren beendet und gegen welchen die Beschwerde in Strafsachen gemäss <ref-law> zulässig ist.
2.2. Der Beschluss der Strafkammer des Obergerichts des Kantons Solothurn vom 18. März 2021 ist ein selbstständig eröffneter Zwischenentscheid, der das Verfahren nicht abschliesst. Dispositiv-Ziff. 1 des Entscheids betrifft die Frage, inwieweit die Strafkammer des Obergerichts des Kantons Solothurn zur Überprüfung des erstinstanzlichen Urteils vom 10. Dezember 2020 über die (Nicht-) Verwahrung des Beschwerdeführers 2 zuständig ist. Insofern geht es um einen selbstständig eröffneten Entscheid über die Zuständigkeit, gegen welchen die Beschwerde in Strafsachen gemäss <ref-law> zulässig ist. Auf die Beschwerde des Beschwerdeführers 2 ist daher ebenfalls einzutreten.
3.
3.1. Die Beschwerdeführerin 1 rügt, die Beschwerdekammer des Obergerichts gebe ihren Antrag im Beschluss vom 30. März 2021 falsch wieder. Sie habe nicht die Abschreibung des Beschwerdeverfahrens beantragt, sondern dessen Sistierung bis zur rechtskräftigen Erledigung des Berufungsverfahrens. Ein rechtskräftiges obergerichtliches Urteil liege bis dato nicht vor. Aktuell bestehe keine Sicherheit dafür, dass die von der Strafkammer des Obergerichts des Kantons Solothurn im Zwischenentscheid vom 18. März 2021 vertretene Auffassung im Rahmen des vom Beschwerdegegner 1 angekündigten Rechtsmittels auch vom Bundesgericht geteilt werde. Sollte die Rechtsauffassung nicht geschützt werden, sei das Gesuch um Anordnung der Verwahrung im Anschluss an die Aufhebung der stationären und ambulanten Massnahme im Beschwerdeverfahren nach <ref-law> zu beurteilen, was angesichts der rechtskräftigen Erledigung dieses Beschwerdeverfahrens durch Abschreibungsbeschluss nicht mehr möglich wäre. Insofern bestehe ein rechtlich geschütztes Interesse an der Anfechtung des Beschlusses vom 30. März 2021.
3.2. Der Beschwerdeführer 2 kritisiert, die Strafprozessordnung biete keine Grundlage für die Vereinigung eines Nachverfahrens betreffend Verwahrung mit einem Verfahren betreffend eine originäre Verwahrung. Eine solche Verfahrensvereinigung sei gesetzlich nicht vorgesehen und daher nicht möglich. Das erstinstanzliche Gericht könne lediglich in beiden Verfahren gemeinsam entscheiden. Die getrennt voneinander in verschiedenen Verfahren zu beurteilenden Fragen hätten daher richtigerweise nicht in einem einzigen Urteil, sondern in einem Urteil und einem Beschluss abgehandelt werden müssen. Gegen das erstinstanzliche Urteil stehe die Berufung zur Verfügung (<ref-law>) und gegen den selbstständigen nachträglichen Entscheid die Beschwerde im Sinne von <ref-law>. Die funktionellen Zuständigkeiten auf Ebene der Rechtsmittelinstanz seien gemäss §§ 31 und 33bis Abs. 1 lit. a des Gesetzes des Kantons Solothurn vom 13. März 1977 über die Gerichtsorganisation (BGS 125.12) klar voneinander abgegrenzt. Die Vorinstanz vermische die unterschiedlichen Aspekte der beiden Verfahren. Im vorliegenden Nachverfahren stelle sich die Frage, ob nach der Aufhebung einer stationären Massnahme und der darauffolgenden Anordnung einer ambulanten Massnahme bei späterer Aufhebung der ambulanten Massnahme eine Verwahrung angeordnet werden könne. Diese Konstellation sei gesetzlich nicht geregelt. Es sei daher zunächst zu prüfen, ob eine Verwahrung nach Aufhebung einer ambulanten Massnahme mangels gesetzlicher Grundlage überhaupt zulässig sei. Als Anlasstat für die originäre Verwahrung kämen die Vorwürfe aus dem Jahr 2018 in Betracht, wobei die frühere Delinquenz allenfalls im Rahmen der Prognose zu berücksichtigen sei. Es bestehe der Verdacht, dass die Vorinstanz mit der unzulässigen Vermischung der beiden unterschiedlichen Verfahren die Möglichkeit schaffen wolle, ihn auch dann zu verwahren, wenn dies aufgrund der Taten aus dem Jahr 2006 nicht möglich sei, weil aktuell keine stationäre Massnahme aufgehoben worden sei, und eine Verwahrung wegen der Vorwürfe aus dem Jahr 2018 ausgeschlossen sei, weil er diesbezüglich freizusprechen oder die Schwelle der Anlasstat im Sinne von <ref-law> nicht erreicht sei.
3.3.
3.3.1. Gemäss <ref-law> ordnet das Gericht die Verwahrung an, wenn der Täter eine in <ref-law> erwähnte Katalogtat (Mord, vorsätzliche Tötung, schwere Körperverletzung, Vergewaltigung, Raub, Geiselnahme, Brandstiftung oder Gefährdung des Lebens) oder eine andere mit einer Höchststrafe von fünf oder mehr Jahren bedrohte Tat begangen hat, durch die er die physische, psychische oder sexuelle Integrität einer andern Person schwer beeinträchtigt hat oder beeinträchtigen wollte, und wenn aufgrund der Persönlichkeitsmerkmale des Täters, der Tatumstände und seiner gesamten Lebensumstände ernsthaft zu erwarten ist, dass er weitere Taten dieser Art begeht. Zuständig für die Anordnung der Verwahrung ist das Sachgericht, das über die Straftaten zu befinden hat. Der Entscheid über die (originäre) Verwahrung ergeht mit dem Sachurteil (vgl. <ref-law>). Die betroffene Person kann sich dagegen mit dem Rechtsmittel der Berufung (Art. 80 Abs. 1 Satz 1 i.V.m. <ref-law>) zur Wehr setzen.
3.3.2. Die stationäre therapeutische Massnahme im Sinne von <ref-law> wird gemäss <ref-law> aufgehoben, wenn deren Durch- oder Fortführung als aussichtslos erscheint. Ist bei Aufhebung einer Massnahme, die aufgrund einer Straftat nach <ref-law> angeordnet wurde, ernsthaft zu erwarten, dass der Täter weitere Taten dieser Art begeht, so kann das Gericht auf Antrag der Vollzugsbehörde die Verwahrung anordnen (<ref-law>). Bei <ref-law> handelt es sich um die Substitution einer stationären therapeutischen Massnahme durch eine Verwahrung, d.h. um eine Anpassung der früheren Massnahme an eine spätere Entwicklung hinsichtlich des Geisteszustands des Täters oder neuer Behandlungserkenntnisse. Die im StGB vorgesehene Möglichkeit, Massnahmen auszutauschen, ist Ausdruck des Bedürfnisses nach Flexibilität und Durchlässigkeit im Massnahmenrecht. Wird die stationäre therapeutische Massnahme aufgrund von festgestellter Aussichtslosigkeit aufgehoben, kann der therapeutische Zweck nicht weiterverfolgt werden. Stattdessen tritt der Sicherungsgedanke stärker in den Vordergrund (<ref-ruling> E. 1.7 f.; Urteile 6B_381/2021 vom 17. Juni 2021 E. 2.3; 6B_82/2021 vom 1. April 2021 E. 3.3). Bei der nachträglichen Verwahrung gestützt auf <ref-law> handelt es sich um einen selbstständigen nachträglichen gerichtlichen Entscheid im Sinne von <ref-law>, der in Form eines Beschlusses (vgl. <ref-law> e contrario i.V.m. <ref-law>) zu ergehen hat und mit Beschwerde im Sinne von <ref-law> anzufechten ist (<ref-ruling> E. 2.3; <ref-ruling> E. 3 f.).
3.4.
3.4.1. Wird eine ambulante Behandlung wegen Aussichtslosigkeit (<ref-law>), Erreichen der gesetzlichen Höchstdauer (<ref-law>) oder Erfolglosigkeit (<ref-law>) aufgehoben, so kann das Gericht an Stelle des in <ref-law> vorgesehenen Strafvollzugs eine stationäre therapeutische Massnahme nach den Art. 59-61 StGB anordnen, wenn zu erwarten ist, dadurch lasse sich der Gefahr weiterer, mit dem Zustand des Täters in Zusammenhang stehender Verbrechen und Vergehen begegnen (<ref-law>). Der Beschwerdeführer 2 macht daher zu Recht geltend, eine direkte Umwandlung einer ambulanten Massnahme in eine Verwahrung sei gesetzlich nicht vorgesehen und nach der Rechtsprechung daher nicht möglich (<ref-ruling> E. 2 und 3; Urteil 6B_338/2018 vom 22. Mai 2018 E. 2.2.3). Fraglich ist zudem, ob das DdI/SO (vgl. Entscheid vom 4. Dezember 2018) für die Aufhebung der ambulanten therapeutischen Massnahme infolge Aussichtslosigkeit nach Bekanntwerden der neuen Vorwürfe gegenüber dem Beschwerdeführer 2 zuständig war (vgl. <ref-law>).
3.4.2. Vorliegend lag es indes nicht in der Zuständigkeit des Obergerichts, mit Urteil vom 16. September 2016 im Rechtsmittelverfahren betreffend die Verlängerung der stationären therapeutischen Massnahme nach <ref-law> eine ambulante therapeutische Massnahme nach <ref-law> anzuordnen. Das Obergericht des Kantons Solothurn hatte im Urteil vom 16. September 2016 lediglich über die Verlängerung der stationären Massnahme in Anwendung von <ref-law> zu befinden. Für die Aufhebung der stationären therapeutischen Massnahme infolge Aussichtslosigkeit war die Vollzugsbehörde zuständig, d.h. vorliegend das DdI/SO (vgl. <ref-law>). Nach rechtskräftiger Aufhebung der stationären therapeutischen Massnahme ist es am erstinstanzlichen Gericht, auf Antrag der Vollzugsbehörde über die Rechtsfolgen zu befinden, d.h. insbesondere eine andere Massnahme (vgl. <ref-law>) oder gegebenenfalls die Verwahrung (vgl. <ref-law>; oben E. 3.3.2) anzuordnen (zum Ganzen: <ref-ruling> E. 1.3 f.; <ref-ruling> E. 2 und 3; vgl. zum in gewissen Kantonen geltenden sog. "Vollzugsgerichtsmodell": <ref-ruling> E. 1.4 ff.; Urteil 6B_1223/2019 vom 27. März 2020 E. 1 f.). Hinzu kommt, dass die vom Obergericht am 16. September 2016 angeordnete ambulante Massnahme nach der Nichtverlängerung der stationären therapeutischen Massnahme infolge Unbehandelbarkeit wohl nicht der Therapierung des Beschwerdeführers 2 diente, sondern dessen Betreuung nach der Entlassung aus der stationären therapeutischen Massnahme. Der Beschwerdeführer 2 selbst wies in seiner Beschwerde in Strafsachen gegen den obergerichtlichen Entscheid vom 16. September 2016 darauf hin, die ambulante Massnahme stehe im offenen Widerspruch zur fehlenden Behandelbarkeit und die Anordnung einer solchen Massnahme im Verlängerungsverfahren nach <ref-law> sei seines Erachtens nicht zulässig (vgl. Urteil 6B_1213/2016 vom 8. März 2017 E. 1.3). Er hat diese indes explizit nicht angefochten (Urteil, a.a.O., E. 1.3, 3 und 3.3), weshalb darauf nicht zurückzukommen ist.
3.4.3. <ref-law> gelangt dennoch auch in der vorliegenden Konstellation zur Anwendung. Das DdI/SO hob die stationäre therapeutische Massnahme am 13. Oktober 2016 auf, weshalb es im Anschluss daran beim Amtsgericht von Olten-Gösgen in Anwendung von <ref-law> die Verwahrung des Beschwerdeführers 2 beantragen konnte. Dass das Obergericht des Kantons Solothurn im Urteil vom 16. September 2016 als Ersatz für die nicht verlängerte stationäre Massnahme nach <ref-law> (zu Unrecht) eine ambulante therapeutische Massnahme nach <ref-law> anordnete, war nicht geeignet, einen späteren Entscheid über die nachträgliche Verwahrung des Beschwerdeführers 2 nach <ref-law> infolge Aussichtslosigkeit der stationären therapeutischen Massnahme zu verunmöglichen bzw. den Entscheid über dessen Nichtverwahrung vorwegzunehmen.
Entgegen den Ausführungen im Urteil des Amtsgerichts von Olten-Gösgen vom 10. Dezember 2020 (vgl. S. 61) erklärt das Bundesgericht im Urteil 6B_1213/2016 vom 8. März 2017 sodann nicht die Aufhebung der stationären Massnahme als solches für nichtig. Das DdI/SO war nach der Nichtverlängerung der stationären therapeutischen Massnahme durch das Obergericht mit Entscheid vom 16. September 2016 vielmehr verpflichtet, diese aufzuheben (vgl. <ref-law>; oben E. 3.4.2). Das Bundesgericht beanstandete lediglich den Zeitpunkt der Aufhebung, nämlich dass die stationäre therapeutische Massnahme "rückwirkend per 14. Dezember 2014" aufgehoben wurde (Urteil 6B_1213/2016 vom 8. März 2017 E. 4).
3.4.4. Das DdI/SO als Vollzugsbehörde stellte nach dem Gesagten beim Amtsgericht von Olten-Gösgen am 13. Oktober 2016 gestützt auf <ref-law> einen gültigen Antrag auf Verwahrung des Beschwerdeführers 2. Gleichzeitig war die Frage nach der Verwahrung des Beschwerdeführers 2 nach der Anklageerhebung vom 17. Dezember 2019 wegen neuer Anlassdelikte im Sinne von <ref-law> auch im vor dem Amtsgericht von Olten-Gösgen hängigen Strafverfahren gegen den Beschwerdeführer 2 zu beurteilen. Beim Amtsgericht von Olten-Gösgen waren daher zwei gültige Anträge auf Verwahrung des Beschwerdeführers 2 hängig. Weder das StGB noch die StPO regeln, wie in diesem Sonderfall zu verfahren ist. Die Art. 29 f. StPO, welche die Zuständigkeit beim Zusammentreffen mehrerer Straftaten regeln, sind nicht auf Massnahmeverfahren, sondern auf die eigentliche Strafverfolgung zugeschnitten. Sie bezwecken die Verfolgung und Beurteilung von Straftaten in einem einheitlichen Verfahren und dienen der Vermeidung von sich widersprechenden Urteilen, der Prozessökonomie sowie der Gewährleistung des Gleichbehandlungsgebots (Urteil 6B_1223/2019 vom 27. März 2020 E. 1.2).
3.5.
3.5.1. Der in <ref-law> sowie Art. 7 Abs. 1 EMRK verankerte Grundsatz "keine Strafe ohne Gesetz" ist auf dem Gebiet des (Straf-) Prozessrechts nicht anwendbar (POPP/BERKEMEIER, in: Basler Kommentar, Strafrecht, Bd. I, 4. Aufl. 2019, N. 20 zu <ref-law> mit Hinweisen). Indes bedürfen auch strafprozessuale Grundrechtseingriffe bzw. Zwangsmassnahmen einer ausdrücklichen Gesetzesgrundlage (vgl. <ref-law>; Art. 31 Abs. 1 und Art. 36 Abs. 1 BV; WOLFGANG WOHLERS, in: Kommentar zur Schweizerischen Strafprozessordnung [StPO], Donatsch und andere [Hrsg.], 3. Aufl. 2020 [nachfolgend: WOHLERS, Kommentar], N. 13 f. zu <ref-law>; STEFAN HEIMGARTNER, Auslegungs- und Rechtsfindungsmethodik im Strafprozessrecht, AJP 1/2016 S. 3 ff., S. 7 ff.). Generell gilt im Strafverfahren zudem der Grundsatz der Formstrenge. Danach können Strafverfahren nur in den vom Gesetz vorgesehenen Formen durchgeführt und abgeschlossen werden (<ref-law>; <ref-ruling> E. 1.3.2; Botschaft vom 21. Dezember 2005 zur Vereinheitlichung des Strafprozessrechts, BBl 2006 1128 Ziff. 2.1.1 zu Art. 2 E-StPO). Der Grundsatz der Formstrenge ("nullum judicium sine lege"; "principe de la légalité du droit de la procédure pénale") ist auch in der Rechtsprechung des EGMR anerkannt (Urteil des Europäischen Gerichtshofs für Menschenrechte [EGMR] Coëme und weitere gegen Belgien, Nr. 32492/96, 32547/96, 32548/96, 33209/96 und 33210/96, §§ 98 f. und 102; WOHLERS, Kommentar, a.a.O., N. 8 zu <ref-law>). Nach der Rechtsprechung des EGMR handelt es sich dabei um einen allgemeinen Rechtsgrundsatz (Urteil des EGMR Coëme, a.a.O., § 102), der sich aus dem in Art. 6 Ziff. 1 EMRK verankerten Anspruch auf Beurteilung durch ein auf Gesetz beruhendes Gericht ("tribunal établi par la loi") ergibt (Urteil des EGMR Coëme, a.a.O., §§ 98 f.). Verlangt wird, dass das Gericht gewisse verfahrensrechtliche Regeln einhalten muss, um ein faires Verfahren zu garantieren (vgl. Urteil des EGMR Coëme, a.a.O., §§ 99 und 102). Die konkrete Umsetzung des Grundsatzes der Formstrenge erfolgt einerseits durch die Verpflichtung, das Strafverfahren nach den in den Art. 3 -11 StPO kodifizierten Grundsätzen und unter Beachtung der Vorgaben der BV sowie der EMRK durchzuführen, und andererseits dadurch, dass die gesetzlich abschliessend normierten Möglichkeiten der Verfahrenserledigung (insb. Nichtanhandnahme gemäss <ref-law>, Einstellung gemäss <ref-law>, Anklageerhebung im ordentlichen oder abgekürzten Verfahren gemäss Art. 324 ff. und 358 ff. StPO, Erlass eines Strafbefehls gemäss <ref-law>) strikte zu beachten sind (<ref-ruling> E. 1.3.2; STRAUB/WELTERT, in: Basler Kommentar, Strafprozessordnung/Jugendstrafprozessordnung, 2. Aufl. 2014, N. 12 zu <ref-law>; WOHLERS, Kommentar, a.a.O., N. 10 ff. und N. 16 ff. zu <ref-law>). Ziel des Grundsatzes der Formstrenge ist es, die Justizförmigkeit des Strafverfahrens zu gewährleisten (<ref-ruling> E. 1.3.2; WOHLERS, Kommentar, a.a.O., N. 7 f. zu <ref-law>). Die schützenden Förmlichkeiten des Strafverfahrens sind kein Selbstzweck, sondern dienen der Gewährleistung der Fairness des Verfahrens, indem sie Machtmissbrauch und willkürlich-rechtsungleiche Behandlung ausschliessen und unangemessene Beeinträchtigungen der Verteidigungsrechte verhindern (WOHLERS, Kommentar, a.a.O., N. 8 zu <ref-law>; vgl. auch Urteil des EGMR Coëme, a.a.O., § 102). Zusätzlich kommt der Förmlichkeit des Verfahrens auch wahrheitsverbürgende Funktion zu (WOHLERS, Kommentar, a.a.O., N. 8 zu <ref-law>; ausführlich dazu sowie zur historischen Entwicklung der Formstrenge im Strafprozess auch: DERS., Die schützende Förmlichkeit des Strafprozessrechts: Zur aktuellen Bedeutung (slosigkeit) eines "alteuropäischen" Konzepts, in: Für die Sache - Kriminalwissenschaften aus unabhängiger Perspektive, Festschrift für Ulrich Eisenberg zum 80. Geburtstag, 2019 [nachfolgend: WOHLERS, Festschrift Eisenberg], S. 593 ff.).
Strafverfahren dürfen deshalb nicht informell, beispielsweise durch Abschreibung mittels Aktenvermerk, erledigt werden (BBl 2006 1128 Ziff. 2.1.1 zu Art. 2 E-StPO; WOHLERS, Kommentar, a.a.O., N. 16 zu <ref-law>; STRAUB/WELTERT, a.a.O., N. 12 zu <ref-law>). Der Grundsatz der Formstrenge ist zudem verletzt, wenn in einem selbstständigen Massnahmeverfahren gegen eine schuldunfähige beschuldigte Person im Sinne von Art. 374 f. StPO ohne ein vorgängiges ordentliches Untersuchungsverfahren und ohne Anklageerhebung ein Schuldspruch ergeht (<ref-ruling> E. 1.3 f.). Der EGMR bejahte einen Verstoss gegen den Grundsatz der Förmlichkeit des Strafverfahrens ("principe de la légalité du droit de la procédure pénale") mangels Voraussehbarkeit weiter, wo strafprozessuale Regeln gänzlich fehlten bzw. das geltende ordentliche Strafprozessrecht nur soweit für (sinngemäss) anwendbar erklärt wurde, als dies mit den Besonderheiten des konkreten Verfahrens vereinbar war (Urteil des EGMR Coëme, a.a.O., §§ 100 ff.), sowie bei einer gesetzlich nicht vorgesehenen Vereinigung von konnexen Strafverfahren gegen mehrere Beschuldigte (Beteiligte) zwecks Vermeidung widersprüchlicher Urteile sowie aus prozessökonomischen Gründen bei einem bezüglich einzelner Beschuldigter unzuständigen Gericht (Urteil des EGMR Coëme, a.a.O., §§ 105 ff.). Darüber hinaus kommt die schützende Förmlichkeit des Strafprozessrechts insbesondere bei der Beurteilung von Beweisverwertungsverboten bei fehlerhafter Beweisgewinnung und/oder -erhebung zum Tragen (vgl. WOHLERS, Festschrift Eisenberg, a.a.O., S. 593 ff.).
3.5.2. Der Grundsatz der Formstrenge (<ref-law>) steht einer Gesetzesauslegung und einer richterlichen Lückenfüllung jedoch nicht entgegen. Es gehört insbesondere hinsichtlich organisationsrechtlicher Bestimmungen der StPO, um welche es hier geht, vielmehr zu den Aufgaben der Justiz, das Gesetz sachgerecht auszulegen und allfällige Lücken "modo legislatoris" zu füllen (ausführlich dazu: HEIMGARTNER, a.a.O., insb. S. 3 ff. und 6 ff.), zumal der Gesetzgeber nicht alle sich im Strafprozessrecht stellenden Fragen bis ins letzte Detail regeln kann und er die Beantwortung gewisser Fragen teils bewusst der Rechtsprechung überliess. Beansprucht das Legalitätsprinzip (vgl. <ref-law>; Art. 31 Abs. 1 und Art. 36 Abs. 1 BV) keine Geltung, können auf dem Wege der richterlichen Rechtsfindung sowohl echte als auch unechte Lücken der StPO geschlossen werden (HEIMGARTNER, a.a.O., S. 5 f.). Auch die Rechtsprechung des EGMR anerkennt ausdrücklich, dass die gesetzliche Verankerung der strafprozessualen Regeln (bzw. die Pflicht dazu) eine Gesetzesauslegung durch die Gerichte nicht ausschliesst (Urteil des EGMR Coëme, a.a.O., § 98 in fine).
3.5.3. Für die Auslegung von Gesetzesbestimmungen gilt die von der Rechtsprechung entwickelte juristische Methodenlehre. Danach ist das Gesetz in erster Linie aus sich selbst heraus auszulegen, d.h. nach dem Wortlaut, Sinn und Zweck und den ihm zugrunde liegenden Wertungen auf der Basis einer teleologischen Verständnismethode. Die Gesetzesauslegung hat sich vom Gedanken leiten zu lassen, dass nicht schon der Wortlaut die Norm darstellt, sondern erst das an Sachverhalten verstandene und konkretisierte Gesetz. Gefordert ist die sachlich richtige Entscheidung im normativen Gefüge, ausgerichtet auf ein befriedigendes Ergebnis der ratio legis. Das Bundesgericht befolgt einen pragmatischen Methodenpluralismus und lehnt es namentlich ab, die einzelnen Auslegungselemente einer hierarchischen Prioritätsordnung zu unterstellen (zum Ganzen: <ref-ruling> E. 4.1; <ref-ruling> E. 3.1.2; je mit Hinweisen).
3.6.
3.6.1. Offensichtlich ist entgegen der Kritik des Beschwerdeführers 2, dass es in den beiden zuvor beim Amtsgericht von Olten-Gösgen hängigen Verfahren OGSAG.2019.28 und OGSAG.2016.34 um die gleiche Frage ging, nämlich nach der Verwahrung des Beschwerdeführers 2. Bei neuen Anlasstaten im Sinne von <ref-law> muss das für deren Beurteilung zuständige Gericht erneut über eine allfällige Verwahrung entscheiden. Sowohl bei der nachträglichen Verwahrung gestützt auf <ref-law> als auch bei der originären Verwahrung nach <ref-law> muss der Richter für die entscheidende Frage nach der Legalprognose eine Gesamtbetrachtung vornehmen. Die Kriminalitätsentwicklung, d.h. Beginn, Art und Häufigkeit des früheren strafbaren Verhaltens, ist ein entscheidendes Prognosekriterium (HEER/HABERMEYER, in: Basler Kommentar, Strafrecht I, 4. Aufl. 2019, N. 68 zu <ref-law>). Lehre und Rechtsprechung anerkennen daher, dass bei der Verwahrung nach <ref-law> für die Legalprognose nicht nur den neu zu beurteilenden Anlasstaten, sondern - unabhängig von der zwischenzeitlichen Löschung im Strafregister - auch allfälligen Vorstrafen Rechnung zu tragen ist (<ref-ruling> E. 2.5; HEER/HABERMEYER, a.a.O., N. 68 zu <ref-law>). Desgleichen kann bei der Beurteilung einer nachträglichen Verwahrung infolge Aussichtslosigkeit der zuvor angeordneten stationären therapeutischen Massnahme (vgl. <ref-law>) die neue Delinquenz nicht einfach ausgeblendet werden. Eine getrennte Weiterführung der beiden Verfahren war daher weder möglich noch angezeigt.
3.6.2. Das Amtsgericht von Olten-Gösgen (mittels Beschluss vom 4. Juni 2020 und Urteil vom 10. Dezember 2020) und das Obergericht des Kantons Solothurn (in den Beschlüssen vom 8. Juli 2020 und vom 18. März 2021) sprachen sich in der vorliegenden Konstellation daher zu Recht für eine Verfahrensvereinigung und für die abschliessende Beurteilung der hängigen Verfahren betreffend Verwahrung im erstinstanzlichen Strafurteil aus (vgl. <ref-law>). Das Strafverfahren wegen neuer Straftaten, in welchem erneut über die Verwahrung zu befinden ist, geht dem selbstständigen nachträglichen Massnahmeverfahren insofern vor. Dieser Grundsatz liegt auch <ref-law> zugrunde, der bei erneuter Delinquenz nach der bedingten Entlassung aus der stationären therapeutischen Massnahme zur Anwendung gelangt (vgl. Urteil 6B_82/2021 vom 1. April 2021 E. 3).
Da folglich im erstinstanzlichen Strafurteil über die Verwahrung des Beschwerdeführers 2 zu befinden war, ist die Zuständigkeit für die Behandlung dieser Frage im Rechtsmittelverfahren bei der Berufungsinstanz anzusiedeln (<ref-law>). Dies erscheint auch insofern sachgerecht, als zweitinstanzlich nur die Berufungsinstanz darüber entscheiden kann, ob und inwiefern sich der Beschwerdeführer 2 erneut strafbar gemacht hat. Die Beurteilung durch das Berufungsgericht als Rechtsmittelinstanz ermöglicht eine umfassende Überprüfung des gesamten Strafurteils (vgl. Art. 398 Abs. 2 und 3 StPO). Die vom Beschwerdeführer 2 beantragte Zweiteilung wäre demgegenüber nicht sachgerecht, nachdem nicht zwei Gerichtsinstanzen gleichzeitig rechtsgültig über die gleiche Frage der Verwahrung befinden können.
3.6.3. Unbegründet ist der Hinweis des Beschwerdeführers 2 auf das Legalitätsprinzip. Wie dargelegt stehen weder das Legalitätsprinzip noch der in <ref-law> für das Strafprozessrecht verankerte Grundsatz der Formstrenge einer richterlichen Gesetzesauslegung oder gar Lückenfüllung entgegen (oben E. 3.5.2). Zu beurteilen ist vorliegend das Zusammentreffen zweier gesetzlich geregelter Verfahren, d.h. einer nachträglichen Verwahrung gestützt auf <ref-law> und einer originären Verwahrung nach <ref-law>. Es geht um eine punktuelle Gesetzesauslegung hinsichtlich der Frage, ob das erstinstanzliche Gericht in dieser Konstellation über die Verwahrung im Strafurteil oder in Form eines separaten Beschlusses zu entscheiden hat. Zweitinstanzlich wird mit der Berufungsinstanz zudem kein von Gesetzes wegen unzuständiges Gericht, sondern lediglich ein zuständiges Gericht gegenüber einem anderen, a priori ebenfalls zuständigen Gericht (der Beschwerdeinstanz) für ausschliesslich zuständig erklärt. Eine solche Gesetzesauslegung erscheint mit dem in <ref-law> verankerten Grundsatz der Formstrenge ohne Weiteres vereinbar. Damit werden weder das Recht des Beschwerdeführers 2 auf den gesetzlichen Richter noch die Verfahrensrechte des Beschwerdeführers 2 beschnitten, welche sowohl im erstinstanzlichen Verfahren als auch im Verfahren vor dem Berufungsgericht ohne Einschränkungen zu beachten sind. Der Beschwerdeführer 2 beruft sich daher zu Unrecht darauf, die Verfahrensvereinigung sei gesetzlich nicht ausdrücklich vorgesehen.
3.6.4. Die Beschwerde des Beschwerdeführers 2 ist als unbegründet abzuweisen. Mit dem vorliegenden Entscheid wird rechtskräftig über die Verfahrensvereinigung und die Kognition der Berufungsinstanz zur Überprüfung des erstinstanzlichen Urteils vom 10. Dezember 2020 entschieden. Der Antrag der Beschwerdeführerin 1 auf Sistierung des bei der Beschwerdekammer des Obergerichts des Kantons Solothurn hängigen Beschwerdeverfahrens wird damit gegenstandslos.
4.
Die Beschwerde des Beschwerdeführers 2 ist abzuweisen. Die Beschwerde der Beschwerdeführerin 1 ist als gegenstandslos abzuschreiben. Das Gesuch des Beschwerdeführers 2 um unentgeltliche Rechtspflege ist gutzuheissen, da dessen Bedürftigkeit erstellt scheint und die Beschwerde nicht von vornherein aussichtslos war (<ref-law>). Es sind keine Gerichtskosten zu erheben und der Rechtsvertreter des Beschwerdeführers 2 ist aus der Bundesgerichtskasse zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Verfahren 6B_544/2021 und 6B_610/2021 werden vereinigt.
2.
Die Beschwerde des Beschwerdeführers 2 wird abgewiesen.
3.
Die Beschwerde der Beschwerdeführerin 1 wird als gegenstandslos abgeschrieben.
4.
Das Gesuch des Beschwerdeführers 2 um unentgeltliche Rechtspflege wird gutgeheissen.
5.
Es werden keine Kosten erhoben.
6.
Rechtsanwalt Thomas Fingerhuth wird aus der Bundesgerichtskasse mit Fr. 2'000.-- entschädigt.
7.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Solothurn, Beschwerdekammer und Strafkammer, schriftlich mitgeteilt.
Lausanne, 23. August 2021
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Jacquemoud-Rossari
Die Gerichtsschreiberin: Unseld