Sachverhalt:
A.
A._ wurde am 20. Januar 2016 durch die Kantonspolizei wegen Verdachts auf Freiheitsberaubung, Nötigung und Körperverletzung festgenommen. Das Zwangsmassnahmengericht Basel-Landschaft versetzte ihn daraufhin für die vorläufige Dauer von zwei Wochen in Untersuchungshaft. Nachdem die Staatsanwaltschaft Basel-Stadt das Verfahren übernommen hatte, verfügte das Zwangsmassnahmengericht am 29. Januar 2016 die Verlängerung der Untersuchungshaft vorläufig bis zum 29. März 2016, wobei der Tatvorwurf um Drohung und versuchte Vergewaltigung erweitert wurde. A._ wird vorgeworfen, B._, mit der er eine heimliche intime Beziehung geführt hat, am 13./14. Januar 2016 in seiner Wohnung in Basel eingesperrt und sie bedroht, beschimpft und geschlagen zu haben. Ausserdem soll er versucht haben, sie zu vergewaltigen.
Am 24. März 2016 verlängerte das Zwangsmassnahmengericht die Untersuchungshaft erneut für die vorläufige Dauer von acht Wochen bis zum 24. Mai 2016. Eine dagegen erhobene Beschwerde wies das Appellationsgericht des Kantons Basel-Stadt mit Entscheid vom 20. April 2016 ab.
B.
Mit Beschwerde in Strafsachen vom 31. Mai 2016 gelangt A._ an das Bundesgericht und beantragt die Aufhebung der Entscheide des Appellationsgerichts vom 20. April 2016 und des Zwangsmassnahmengerichts Basel-Stadt vom 24. März 2016. Er sei umgehend aus der Untersuchungshaft zu entlassen. Eventualiter sei die Sache zum Erlass einer solchen Anordnung an die Vorinstanz zurückzuweisen. Subeventualiter sei ihm bei der Entlassung unter Strafandrohung jeglicher Kontakt zu B._ und ihren Familienmitgliedern zu verbieten. In prozessualer Hinsicht ersucht er um unentgeltliche Rechtspflege.
Die Staatsanwaltschaft und das Appellationsgericht schliessen auf Abweisung der Beschwerde. Der Beschwerdeführer hat keine Replik eingereicht.

Erwägungen:
1.
Gegen den kantonal letztinstanzlichen Haftentscheid des Appellationsgerichts steht die Beschwerde in Strafsachen offen (Art. 78 Abs. 1 i.V.m. <ref-law>). Der Beschwerdeführer nahm am vorinstanzlichen Verfahren teil und hat als direkt betroffener Adressat des angefochtenen Entscheids ein rechtlich geschütztes Interesse an dessen Aufhebung bzw. Änderung. Dieses ist weiterhin aktuell, denn das Zwangsmassnahmengericht Basel-Stadt hat inzwischen die Untersuchungshaft einstweilen bis zum 5. Juli 2016 verlängert, wobei es präzisierte, der Beschuldigte werde aus der Haft entlassen, wenn das Bundesgericht den Entscheid des Appellationsgerichts nicht bestätige. Der Beschwerdeführer ist mithin zur Beschwerde legitimiert (<ref-law>). Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass.
2.
Gemäss <ref-law> ist Untersuchungshaft nur zulässig, wenn die beschuldigte Person eines Verbrechens oder Vergehens dringend verdächtig ist und ein im Gesetz genannter Haftgrund vorliegt. Überdies hat die Haft wie alle strafprozessualen Zwangsmassnahmen verhältnismässig zu sein (vgl. <ref-law>) und sie darf nicht länger dauern als die zu erwartende Freiheitsstrafe (<ref-law>).
3.
Der Beschwerdeführer stellt den dringenden Tatverdacht der Beschimpfung und Körperverletzung nicht in Abrede. Indessen bestreitet er diesen mit Bezug auf die Freiheitsberaubung und die versuchte Vergewaltigung.
3.1. Die Vorinstanz bemerkte dazu, die vom Beschwerdeführer geltend gemachten Widersprüche in den Aussagen des Opfers hinsichtlich ihrer Paarbeziehung, des angeblichen Eheversprechens, der früheren intimen Kontakte mit anderen Männern und den Falschangaben gegenüber ihren Eltern und ihrem Freund beträfen nicht das Kerngeschehen. Der dringende Tatverdacht der Freiheitsberaubung sei erstellt, stünden die Aussagen der Geschädigten, wonach er sie mit Gewalt am Verlassen der Wohnung gehindert habe, doch nicht im Widerspruch zur Sachlage. Mit Bezug auf den Vorwurf der mehrfachen versuchten Vergewaltigung sei zwar richtig, dass die Anzeigestellerin diesen bei ihrer ersten Einvernahme am 14. Januar 2016 unerwähnt liess. Sie habe ihn aber bereits am 18. Januar 2016 und damit relativ zeitnah zu den inkriminierten Geschehnissen erhoben. Die anfänglich zaghaften und teilweise korrigierenden Aussagen des mutmasslichen Opfers insbesondere hinsichtlich der intimen Beziehung zum Beschwerdeführer liessen sich mit dem kulturellen und gesellschaftlichen Hintergrund der Beteiligten zwanglos erklären. So habe sie mehrmals deutlich geäussert, dass sie sich gegenüber ihren Eltern für ihr - aus deren Sicht - unpassendes Verhalten zum anderen Geschlecht schäme. Vor diesem Hintergrund sei es denn auch stimmig, wenn sie ausgesagt habe, der Beschwerdeführer habe sie just damit unter Druck gesetzt und gedroht, ihren Eltern von den Männerbekanntschaften und vorehelichen Sexualkontakten zu erzählen. Ebenso nachvollziehbar sei, dass sie mit diesen Details erst im Laufe der Befragungen rausgerückt sei und den Oralverkehr nicht freimütig eingeräumt habe. Ins kulturelle Bild passe auch, dass der Beschwerdeführer sie durch manuelle Entjungferung zur Heirat habe zwingen wollen, nachdem sie sich erfolgreich gegen eine Vergewaltigung zur Wehr gesetzt habe. Schliesslich passe auch ihre Beeinflussbarkeit durch den Freund ins Bild einer in zwischengeschlechtlichen Fragen unsicheren und von konservativen kulturellen Wertvorstellungen geprägten jungen Frau. Ihre Aussagen hinsichtlich des Kerngeschehens seien im Wesentlichen stimmig. Auch habe sie die erhobenen Vorwürfe in der Konfrontationseinvernahme vom 16. März 2016 neuerlich detailliert bestätigt.
3.2. Der Beschwerdeführer wendet dagegen im Wesentlichen ein, die lange Dauer der Untersuchungshaft liesse sich höchstens bei einem dringenden Tatverdacht der Freiheitsberaubung und der versuchten Vergewaltigung rechtfertigen, den die Vorinstanz zu Unrecht bejaht habe. In Situationen, in denen es Aussage gegen Aussage stehe, werde ohne weitere Beweismittel in aller Regel im Zweifel zugunsten des Beschuldigten entschieden. Da sich der Tatverdacht einzig auf die Aussagen des vermeintlichen Opfers stütze, seien hohe Anforderungen an dessen Glaubwürdigkeit zu stellen, wobei das gesamte Aussageverhalten zu würdigen sei. Die mutmasslich Geschädigte habe sich in Widersprüche verwickelt und mehrere unstimmige Angaben gemacht. So habe sie zuerst ausgesagt, ein ihr gänzlich Unbekannter habe sie unter Zwang in die Wohnung gezerrt. Später habe sie jedoch eingeräumt, den Täter zu kennen und freiwillig in seine Wohnung gegangen zu sein. Der Beschuldigte sei im Verlaufe der Einvernahmen vom Bekannten zum Liebhaber bis hin zum Verlobten mutiert, mit dem sie mindestens zwei Mal Oralverkehr gehabt habe. Auch hinsichtlich der Intimkontakte mit dem Beschuldigten habe sie zunächst keine solchen erwähnt. Während der zweiten Einvernahme habe sie jedoch behauptet, es sei zu Vergewaltigungsversuchen gekommen, wobei sie in jener Nacht auch noch einvernehmlichen Intimkontakt gehabt hätten. Unstimmigkeiten im Aussageverhalten ergäben sich ferner hinsichtlich des Motivs für die Gewalt und der Angaben über sich gegenüber ihren engsten Bezugspersonen. Ausserdem stimme ihre Aussage über die Anzahl verwendeter Kondome nicht mit der Sachlage überein. Hinzu kämen Indizien, die dafür sprächen, dass sie in Absprache oder unter Einfluss ihres neuen Freundes Falschangaben gemacht oder auf Beweismittel eingewirkt habe. Insgesamt sei das Aussageverhalten des vermeintlichen Opfers daher unzuverlässig und nicht geeignet, einen erhärteten Tatverdacht zu begründen. Es bestehe vielmehr der Verdacht, dass dieses die Verantwortung für das in seiner Kultur verwerfliche Verhalten auf den Beschuldigten abschieben wolle.
3.3.
3.3.1. Der Beschwerdeführer macht damit vor Bundesgericht im Wesentlichen die gleichen Einwände geltend, wie vor dem Appellationsgericht. Dieses hat sich mit diesen einlässlich auseinandergesetzt, wobei der angefochtene Entscheid nicht zu beanstanden ist. Auf die Erwägungen der Vorinstanz zum dringenden Tatverdacht kann somit verwiesen werden (vgl. E. 2.4 des Entscheids vom 20. April 2016).
3.3.2. Mit seinen Vorbringen übersieht der Beschwerdeführer insbesondere, dass das Bundesgericht bei der Überprüfung des allgemeinen Haftgrundes des dringenden Tatverdachts keine erschöpfende Abwägung sämtlicher belastender und entlastender Beweisergebnisse vorzunehmen hat. Macht ein Inhaftierter geltend, er befinde sich ohne ausreichenden Tatverdacht in strafprozessualer Haft, ist vielmehr zu prüfen, ob aufgrund der bisherigen Untersuchungsergebnisse genügend konkrete Anhaltspunkte für ein Verbrechen oder Vergehen und eine Beteiligung des Beschwerdeführers an dieser Tat vorliegen, die Justizbehörden somit das Bestehen eines dringenden Tatverdachts mit vertretbaren Gründen bejahen durften. Im Haftprüfungsverfahren genügt dabei der Nachweis von konkreten Verdachtsmomenten, wonach das untersuchte Verhalten mit erheblicher Wahrscheinlichkeit die fraglichen Tatbestandsmerkmale erfüllen könnte (vgl. <ref-ruling> E. 3.2 S. 126; <ref-ruling> E. 3c S. 146).
3.3.3. Soweit der Beschwerdeführer kritisiert, die Vorinstanz habe nicht zwischen Tatbeständen unterschieden, die eine Haftverlängerung rechtfertigten und solchen, die dies nicht täten, findet sein Vorwurf keine Stütze in den Erwägungen des angefochtenen Entscheids: Das Appellationsgericht hat den dringenden Tatverdacht mit Bezug auf alle vorgeworfenen Straftatbestände als gegeben erachtet, weshalb sich eine Differenzierung nicht aufdrängte. Wenig stichhaltig ist ausserdem sein Vorbringen zur sog. "Aussage-gegen-Aussage-Konstellation". Eine solche muss keineswegs zwingend gestützt auf den Grundsatz "in dubio pro reo" zu einem Freispruch führen (vgl. Urteil 1B_171/2015 vom 27. Mai 2015 E. 5.4.1). Aufgrund des Beschleunigungsgebots in Haftsachen (<ref-law>) hat das Bundesgericht im Haftprüfungsverfahren zur Frage des dringenden Tatverdachts bzw. zur Schuldfrage weder ein eigentliches Beweisverfahren durchzuführen noch dem erkennenden Strafrichter vorzugreifen. Stuft die Vorinstanz gestützt auf eine vertretbare summarische Beweiswürdigung die Aussagen der Privatklägerin als glaubhafter ein als jene des Beschwerdeführers und kommt sie aufgrund dessen im Ergebnis zum Schluss, eine Verurteilung erscheine wahrscheinlich, verletzt dies kein Bundesrecht (vgl. <ref-ruling> E. 3.3 S. 127).
3.3.4. Die mutmasslich Geschädigte hat den Beschwerdeführer in der Untersuchung schwer belastet. Sie hat den Tathergang erstmals anlässlich der Einvernahme vom 19. Januar 2016 detailliert geschildert. Ihre Aussagen in den weiteren Einvernahmen, auch in der Konfrontationseinvernahme vom 16. März 2016, stimmen im Wesentlichen damit überein. Dies trifft insbesondere auf die Angaben im Kernbereich zu, wonach sie nicht freiwillig mit ihm in seine Wohnung gegangen sei und er sie daran gehindert haben soll, diese zu verlassen. Er habe sie zunächst ins Badezimmer eingesperrt, wo er sie geschlagen habe. In der Nacht habe er sie sodann entjungfern wollen, damit er dies ihren Eltern erzählen könne, so dass sie ihn heiraten müsse. Im Wohnzimmer habe er an ihren Kleidern gerissen und sie ausgezogen, was sie aus Angst zugelassen habe. Im Bett habe er gegen ihren Willen mehrfach versucht in sie einzudringen, was ihm aber nicht gelungen sei, da sie die Beine zusammengehalten und gesagt habe, dass er ihr wehtue.
Im Gegensatz dazu wirken die Aussagen des Beschwerdeführers anlässlich der Konfrontationseinvernahme insbesondere hinsichtlich der angeblichen sexuellen Kontakte übertrieben und wenig plausibel. In seiner Rechtsschrift an das Bundesgericht kritisiert er das Aussageverhalten des mutmasslichen Opfers in genereller Weise, indem er vermeintliche Widersprüche und Falschangaben aufzeigt. Diese Einwände vermögen jedoch die Glaubwürdigkeit der Aussagen der mutmasslich Geschädigten nicht zu schmälern. Zwar trifft es zu, dass sie anlässlich der ersten Einvernahme am 14. Januar 2016 namentlich den Vorwurf der versuchten Vergewaltigung nicht erhoben hat. Dies erscheint aber aufgrund ihrer persönlichen und familiären Verhältnisse sowie der konservativen gesellschaftlichen und kulturellen Wertvorstellungen in ihrem Umfeld durchaus begreiflich. Zwar nahmen ihre Eltern nicht persönlich an dieser Einvernahme teil; diese fand jedoch an ihrem Wohnort statt, weshalb sie sich nach eigenen Angaben gefürchtet habe, von den sexuellen Übergriffen zu erzählen, zumal ihre Eltern zugegen waren. In diesem Zusammenhang räumt auch der Beschwerdeführer ein, der soziale und kulturelle Hintergrund könnte das Aussageverhalten der angeblich Geschädigten erklären. Es ist daher mit der Vorinstanz davon auszugehen, dass es ihr sicherlich schwer gefallen ist, über die Vorfälle in der Nacht vom 13. auf den 14. Januar 2016 zu sprechen und intime Fragen dazu zu beantworten. Insoweit erscheint auch nachvollziehbar, wenn sie erst nach und nach davon erzählt hat. Ihre Schilderungen in den Einvernahmen erweisen sich im Kernbereich als konstant, differenziert, detailliert und nicht stereotyp. Mithin können ihre Aussagen als glaubhaft betrachtet werden.
3.3.5. Zu weiteren Vorbringen, die nicht den strafrechtlichen Kernvorwurf, sondern Nebenpunkte der Untersuchung betreffen, hat sich der Haftrichter nicht zu äussern. Dazu gehört namentlich die Frage, ob eine Paarbeziehung bestanden bzw. ob ein Eheversprechen vorgelegen hat oder ob die angeblich Geschädigte gegenüber ihren engsten Bezugspersonen falsche Angaben gemacht hat. Auch zu Details der Beweiswürdigung, die dem Sachrichter vorbehalten bleibt, hat sich das Haftgericht nicht vorgreifend und verfrüht zu äussern. Dies gilt insbesondere für einen angeblichen Widerspruch hinsichtlich der Anzahl verwendeter Kondome und der Beeinflussung des mutmasslichen Opfers durch seinen Freund.
3.3.6. Nach dem Gesagten hat die Vorinstanz demnach kein Bundesrecht verletzt, wenn sie aufgrund der bisherigen Untersuchungsergebnisse davon ausgegangen ist, es bestehe ein dringender Tatverdacht auf Verbrechen oder Vergehen.
4.
Der Beschwerdeführer wendet sich auch gegen die Annahme des besonderen Haftgrunds der Kollusionsgefahr.
4.1. Die Vorinstanz begründet dessen Vorliegen insbesondere damit, dass dem Beschwerdeführer im Falle einer Verurteilung eine empfindliche Sanktion drohe, zumal er teilweise einschlägig vorbestraft sei. Da er den Vorwurf der versuchten Vergewaltigung stets bestritten habe, sei sein Interesse erheblich, das mutmassliche Opfer in seinem Sinne zu beeinflussen. Zudem habe der Beschwerdeführer gerade durch sein hier inkriminiertes Verhalten offenbart, dass er geneigt sei, seinen Willen mit Gewalt durchzusetzen. Weil der Hauptvorwurf auf den Aussagen der mutmasslich Geschädigten beruhe, werde sie in der Regel vom erkennenden Gericht noch einmal befragt. Insofern liege weiterhin Kollusionsgefahr vor.
4.2. Diese Erwägungen sind nicht zu beanstanden. Was der Beschwerdeführer dagegen einwendet, lässt die Annahme von Verdunkelungsgefahr nicht als bundesrechtswidrig erscheinen. Bei den ihm zur Last gelegten Straftaten handelt es sich um schwere Delikte. Bei deren Beurteilung durch den Sachrichter kommt den Aussagen der mutmasslich Geschädigten eine zentrale Bedeutung zu, zumal der Beschwerdeführer namentlich in Bezug auf den Vorwurf der Freiheitsberaubung und der versuchten Vergewaltigung nicht geständig ist. Dass es sich dabei um Beziehungsdelikte handelt, erhöht die Wahrscheinlichkeit einer Beeinflussung durch den Beschwerdeführer im Falle einer Haftentlassung. Zwar ist das Strafverfahren relativ weit vorangeschritten und eine Konfrontationseinvernahme hat bereits stattgefunden. Die Annahme der Vorinstanz, wonach die Geschädigte im Rahmen der erstinstanzlichen Hauptverhandlung erneut zu befragen sein wird, so dass das Gericht einen persönlichen Eindruck von ihr gewinnen kann, erscheint jedoch nachvollziehbar (vgl. Urteile 1B_152/2014 vom 15. Mai 2014 E. 3.4.1; 1B_188/2012 vom 19. April 2012 E. 3.6) und wird auch vom Beschwerdeführer nicht in Abrede gestellt. Entgegen seiner Auffassung begründet der Umstand, dass er im Falle einer Verurteilung mit einer empfindlichen Strafe rechnen muss, einen erheblichen Anreiz, die noch junge Geschädigte zu einer Relativierung oder sogar zu einem Widerruf ihrer belastenden Aussagen zu veranlassen. Überdies hat er ihr gegenüber unbestrittenermassen bereits Gewalt angewendet und sie beschimpft. Dass er dies bloss aus Wut und Enttäuschung gemacht habe, tut der davon ausgehenden Gefahr für die Wahrheitsfindung im Strafverfahren keinen Abbruch. Auch geht sein Einwand, wonach er trotz Kenntnis der Strafanzeige nach seiner ersten Einvernahme bis zur Festnahme nicht kolludiert habe, insoweit fehl, als damals der Vorwurf der versuchten Vergewaltigung noch nicht im Raum stand und es somit auch keinen ernsthaften Anlass für ein Einwirken auf das Opfer gab. Mithin bestehen keine bloss abstrakten Anhaltspunkte für die Annahme von Kollusionsgefahr, die auf der Höhe der drohenden Sanktion und der Bestreitung der Tatvorwürfe basierten. Vielmehr ergibt sich die Verdunkelungsgefahr aus den konkreten Umständen des vorliegenden Falls. Dass es angeblich seitens der Geschädigten zu Beeinflussungsversuchen gekommen sei, vermag daran nichts zu ändern.
4.3. Eine Gesamtwürdigung der Umstände lässt nach dem Ausgeführten eine Kollusionsgefahr trotz der fortgeschrittenen Strafuntersuchung als ernsthaft möglich erscheinen, weshalb die Vorinstanz den Haftgrund nach <ref-law> zu Recht bejaht hat. Es kann daher offen bleiben, ob neben Kollusionsgefahr auch der besondere Haftgrund der Fortsetzungsgefahr erfüllt wäre. Zu einer solchen Prüfung musste sich auch die Vorinstanz nicht veranlasst sehen.
5.
Schliesslich macht der Beschwerdeführer geltend, die Untersuchungshaft sei unverhältnismässig. Soweit er dabei vorbringt, anstelle von Haft sei ein Kontaktverbot unter Strafandrohung auszusprechen, erscheint seine Forderung nicht zwecktauglich zu sein. Denn er bemerkt dazu, der Sachrichter würde es sicherlich zu würdigen wissen, wenn der Beschuldigte gegen ein solches Kontaktverbot verstiesse und wenn das Opfer alsdann "etwas gänzlich Anderes" aussagen würde. Mithin glaubt selbst er nicht ernsthaft daran, dass der Haftzweck mit einer weniger einschneidenden Massnahme erreicht werden kann. Angesichts der erheblichen Kollusionsgefahr erweist sich ein Kontaktverbot nicht als geeignet, eine von Beeinflussungsversuchen freie Sachverhaltsermittlung zu ermöglichen.
Ausserdem erscheint auch die bisherige Haftdauer nicht als unverhältnismässig. Der Beschwerdeführer befindet sich seit bald fünf Monaten in Untersuchungshaft. Beim jetzigen Stand der Untersuchung droht ihm im Falle einer Verurteilung wegen Freiheitsberaubung, versuchter Vergewaltigung, Körperverletzung, Beschimpfung, Drohung und Nötigung eine deutlich längere Freiheitsstrafe. Die Rüge der strafprozessualen Überhaft erweist sich daher ebenfalls als unbegründet.
6.
Nach dem Ausgeführten ist die Beschwerde abzuweisen. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer grundsätzlich kostenpflichtig (<ref-law>). Er ersucht indessen um unentgeltliche Rechtspflege und Verbeiständung. Da die gesetzlichen Voraussetzungen als erfüllt erscheinen, kann dem Gesuch stattgegeben werden (<ref-law>). Demnach ist dem Vertreter des Beschwerdeführers eine angemessene Entschädigung auszurichten.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
3.
Es werden keine Gerichtskosten erhoben.
4.
Dem Vertreter des Beschwerdeführers, Rechtsanwalt Dr. Markus Wick, wird aus der Bundesgerichtskasse eine Entschädigung von Fr. 1'500.-- ausgerichtet.
5.
Dieses Urteil wird dem Beschwerdeführer, der Staatsanwaltschaft des Kantons Basel-Stadt und dem Appellationsgericht des Kantons Basel-Stadt, Einzelgericht, schriftlich mitgeteilt.
Lausanne, 17. Juni 2016
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Merkli
Die Gerichtsschreiberin: Pedretti