Sachverhalt:
A.
Das Regionalgericht Bern-Mittelland sprach X._ am 27. August 2013 des Diebstahls, begangen am frühen Morgen des 6. Juni 2010 zum Nachteil von A._, schuldig und verurteilte ihn zu einer Freiheitsstrafe von 45 Tagen. Es stellte fest, dass die ausgesprochene Freiheitsstrafe vollumfänglich durch Haft erstanden ist und sprach ihm eine Genugtuung von Fr. 20'600.-- für die erlittene Überhaft zu. Gleichzeitig sprach es X._ vom Vorwurf der Vergewaltigung zum Nachteil von A._ frei.
B.
Die Generalstaatsanwaltschaft des Kantons Bern erhob Berufung gegen das Urteil des Regionalgerichts Bern-Mittelland. Das Obergericht des Kantons Bern bestätigte am 18. August 2014 den Freispruch vom Vorwurf der Vergewaltigung. Es sprach X._ des Raubes schuldig und verurteilte ihn zu einer Freiheitsstrafe von 10 Monaten, unter Anrechnung der Untersuchungs- und Sicherheitshaft sowie des vorzeitigen Strafvollzugs von insgesamt 251 Tagen.
Das Obergericht geht von folgendem Sachverhalt aus: X._ traf am 6. Juni 2010 frühmorgens in Bern bei der Lorrainebrücke auf A._, welche gerade mit einem anderen Mann über den Erwerb von Medikamenten sprach. Nachdem sich dieser entfernt hatte, anerbot X._, ihr bei der Suche nach dem Medikament behilflich zu sein, wenn sie im Gegenzug Geschlechtsverkehr mit ihm habe. Gemeinsam gingen sie anschliessend über eine Treppe zu einem Weg hinunter und vollzogen dort den Geschlechtsakt. Eine Gewaltanwendung bzw. der Einsatz eines Messers kann X._ in dieser ersten Phase nicht nachgewiesen werden. In einer zweiten Phase entwendete X._ Bargeld im Betrag von Fr. 305.-- sowie ein Mobiltelefon aus der Handtasche von A._, wobei er ihr kurz an den Hals griff respektive sie würgte.
C.
X._ führt Beschwerde in Strafsachen. Er beantragt, das Urteil des Obergerichts sei aufzuheben. Er sei des Diebstahls schuldig zu sprechen und mit einer Freiheitsstrafe von 45 Tagen zu bestrafen. Eventualiter sei das vorinstanzliche Urteil aufzuheben und zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Für das bundesgerichtliche Verfahren ersucht X._ um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.
D.
Die Gegenparteien sowie die Vorinstanz reichten innert Frist keine Stellungnahmen ein.

Erwägungen:
1.
Der Beschwerdeführer wirft der Vorinstanz eine willkürliche Beweiswürdigung (<ref-law>) und die Verletzung der Unschuldsvermutung (<ref-law>, <ref-law> und Art. 6 Ziff. 2 EMRK) vor.
1.1. Die vorinstanzliche Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; vgl. auch Art. 105 Abs. 1 und 2 BGG). Offensichtlich unrichtig im Sinne von <ref-law> ist die Sachverhaltsfeststellung, wenn sie willkürlich ist (<ref-ruling> E. 10.1 mit Hinweisen; vgl. zum Begriff der Willkür <ref-ruling> E. 2.1; <ref-ruling> E. 3.2.5; <ref-ruling> E. 7.1; je mit Hinweisen).
Inwiefern das Sachgericht den Grundsatz "in dubio pro reo" als Beweiswürdigungsregel verletzt hat, prüft das Bundesgericht ebenfalls unter dem Gesichtspunkt der Willkür. Diese aus der Unschuldsvermutung abgeleitete Maxime wurde wiederholt dargelegt, worauf zu verweisen ist (<ref-ruling> E. 2a mit Hinweisen).
Die Rüge der Verletzung von Grundrechten (einschliesslich Willkür bei der Sachverhaltsfeststellung) muss in der Beschwerde anhand des angefochtenen Entscheids präzise vorgebracht und substanziiert begründet werden, anderenfalls darauf nicht eingetreten wird (<ref-law>; <ref-ruling> E. 2.2; <ref-ruling> E. 3.2; <ref-ruling> E. 4.2.3 136 I 65 E. 1.3.1; je mit Hinweisen).
1.2. Der Beschwerdeführer bestreitet, die Beschwerdegegnerin gewürgt zu haben. Er macht im Wesentlichen geltend, die Beschwerdegegnerin habe immer wieder neue Versionen des Tatgeschehens aufgetischt. Zunächst habe sie nur von einem Würgen gesprochen. Ein weiteres Mal habe sie angegeben, mit einem Messer bedroht worden zu sein. Später sei nur noch von einem Messer, jedoch von keinem Würgen mehr die Rede gewesen. Die Aussagen der Beschwerdegegnerin seien widersprüchlich und unglaubhaft, weshalb darauf nicht abgestellt werden könne. Demgegenüber seien seine eigenen Aussagen konstant und widerspruchsfrei.
Die übrigen Beweismittel sprächen ebenfalls gegen die Aussagen der Beschwerdegegnerin. Gemäss dem forensisch-toxikologischen Gutachten des Instituts für Rechtsmedizin der Universität Bern (IRM) vom 1. November 2010 seien bei der Beschwerdegegnerin zum Tatzeitpunkt ein Diazepam-Spiegel im hochtherapeutischen, Nordiazepam im toxischen und Oxazepam im subtherapeutischen Bereich festgestellt worden. Das Gutachten des IRM zur körperlichen Untersuchung bestätige zudem das Fehlen von Würgemalen. Schliesslich stamme das sichergestellte DNA-Profil am Hals der Beschwerdegegnerin gerade nicht vom Beschwerdeführer, sondern höchstwahrscheinlich von ihr selbst. Wenn die Vorinstanz bei dieser Beweislage ein Würgen seitens des Beschwerdeführers beziehungsweise einen Raub bejahe, verfalle sie in Willkür und verletze den Grundsatz in dubio pro reo.
1.3. Die Glaubhaftigkeit einer konkreten Aussage wird durch methodische Analyse ihres Inhalts darauf überprüft, ob die auf ein bestimmtes Geschehen bezogenen Angaben einem tatsächlichen Erleben des Zeugen entspringen. Damit eine Aussage als zuverlässig gewürdigt werden kann, ist sie insbesondere auf das Vorhandensein von Realitätskriterien und umgekehrt auf das Fehlen von Phantasiesignalen zu überprüfen. Dabei wird zunächst davon ausgegangen, dass die Aussage gerade nicht realitätsbegründet ist, und erst wenn sich diese Annahme (Nullhypothese) aufgrund der festgestellten Realitätskriterien nicht mehr halten lässt, wird geschlossen, dass die Aussage einem wirklichen Erleben entspricht und wahr ist (<ref-ruling> E. 4.3 mit Hinweisen). Die Prüfung der Glaubhaftigkeit von Aussagen ist primär Sache der Gerichte.
1.4. Die Vorinstanz hat hinsichtlich des Tatgeschehens eine umfassende Aussagenanalyse im Sinne der Rechtsprechung vorgenommen. Sie erwägt, der Beschwerdeführer habe zunächst bestritten, etwas mit der Sache zu tun gehabt zu haben. Später habe er zum Tatgeschehen ausgesagt und den Diebstahl eingeräumt. Seine Aussagen seien konstant und widerspruchsfrei. Sie wirkten zudem ehrlich und erlebnisbasiert. Das Aussageverhalten spreche für die Glaubhaftigkeit seiner Aussagen. Demgegenüber enthielten die Aussagen der Beschwerdegegnerin zwar einerseits verschiedene Realitätskriterien, andererseits aber auch diverse Widersprüche und Ungenauigkeiten hinsichtlich des Kerngeschehens. Es seien Aggravierungstendenzen erkennbar. Ihre Schilderungen seien teilweise nicht nachvollziehbar. Gegen die Glaubhaftigkeit ihrer Aussagen spreche nebst dem Aussageverhalten auch, dass ihre Angaben in wesentlichen Punkten den weiteren Beweismitteln widersprechen würden.
Bezüglich der angeblichen Vergewaltigung hält die Vorinstanz fest, der von der Beschwerdegegnerin geschilderte Geschehensablauf sei schwer nachvollziehbar. Weder das Gutachten zur körperlichen Untersuchung noch weitere Beweismittel würden gegen die Aussagen des Beschwerdeführers sprechen. Alles in allem lägen zu viele Unklarheiten vor, als dass diesem nachgewiesen werden könnte, die Beschwerdegegnerin mittels Gewalt (Würgen) oder mittels Drohung (Messereinsatz) gegen ihren Willen zum Geschlechtsverkehr gezwungen zu haben.
Hinsichtlich des Würgens gelangt die Vorinstanz zum Schluss, es lasse sich nicht erstellen, dass der Beschwerdeführer die Beschwerdegegnerin bereits vor bzw. während des Geschlechtsverkehrs gewürgt habe. Jedenfalls lasse sich ein Würgen über längere Zeit bzw. ein derart intensives Würgen wie dies die Beschwerdegegnerin geltend mache, nicht mit den Befunden des IRM-Gutachtens vereinbaren. Demnach zeigten sich an ihrem Hals Hautrötungen, welche durch eine "komprimierende Gewalteinwirkung im Sinne von Kratzspuren" entstanden sein könnten. Es sei gestützt darauf davon auszugehen, dass der Beschwerdeführer der Beschwerdegegnerin während des Vorfalls vom 6. Juni 2010, wenn auch nur kurz, mit seiner Hand an den Hals griff bzw. sie gewürgt habe. Dabei geht die Vorinstanz von zwei möglichen Tathergängen aus. Nach der ersten Tatvariante würgte der Beschwerdeführer die Beschwerdegegnerin kurz vor der Wegnahme der Gegenstände, um eine allfällige Gegenwehr zu unterbinden. Nach der zweiten Tatvariante wollte die Beschwerdegegnerin die Wegnahme verhindern, weshalb er ihr an den Hals griff. So oder anders sei die Rötung am Hals nicht anders zu deuten als dass der Beschwerdeführer an den Hals der Beschwerdegegnerin gegriffen respektive diese gewürgt habe, wobei dies vom Ablauf her in Zusammenhang mit der Wegnahme des Mobiltelefons und des Bargeldes gestanden haben dürfte. Da der Beschwerdeführer von Anfang an die Absicht gehabt habe, die Beschwerdegegnerin zu bestehlen, mache diese Annahme Sinn.
1.5. Wie vom Beschwerdeführer unter Hinweis auf die entsprechenden Aktenstellen geltend gemacht, gab die Beschwerdegegnerin immer wieder neue Tatversionen zu Protokoll. Am 6. Juni 2010 und somit unmittelbar nach der Tat sagte sie aus, zwei Männern begegnet zu sein, die ihr Kokain hätten verkaufen wollen. Sie habe dies abgelehnt, woraufhin sich einer der beiden entfernt habe. Der andere, der Beschwerdeführer, habe sie dann die Treppe hinuntergezerrt. Dort habe er ihr zunächst die Tasche entrissen und das Geld sowie das Mobiltelefon gestohlen. Anschliessend habe er sie ins Bord "gepängglet", ihr die Hose heruntergerissen und sie gewürgt. Dann habe er sie vergewaltigt. Plötzlich hätten sie Passanten vorbeigehen gehört. Sie habe aber nicht schreien können, da sie gewürgt worden sei. Den Einsatz eines Messers seitens des Beschwerdeführers erwähnte die Beschwerdegegnerin nicht.
Am 14. Juni 2010 sagte die Beschwerdegegnerin aus, der Beschwerdeführer habe sie gepackt, seine Arme um ihren Oberkörper geschlungen und sie die Treppe hinuntergezerrt. Bereits auf der Treppe habe er sie dann auch noch gewürgt. In der gleichen Einvernahme sagte die Beschwerdegegnerin aus, der Beschwerdeführer habe sie mit der rechten Hand von vorne gewürgt bis sie unten beim Tatort angekommen seien. Sie habe das Gefühl gehabt, ersticken und sterben zu müssen. Unten angekommen habe er sie mit einer Hand gewürgt und mit der anderen ihre Handtasche entrissen. Daraus habe er das Portemonnaie und das Mobiltelefon genommen. Er habe ihr plötzlich ein Messer an den Hals gehalten und sie bedroht. Anschliessend habe er sie vergewaltigt. Während der Vergewaltigung habe er sie mit der rechten Hand gewürgt und in der linken Hand das Messer rund 30 Zentimeter von ihr entfernt gehalten. Nach der Vergewaltigung habe er ihr das Messer erneut an den Hals gesetzt. Auf die Frage, wie das Messer ausgesehen habe, sagte sie, dieses nicht gesehen, sondern nur am Hals gespürt zu haben. Kurz zuvor in derselben Einvernahme gab sie an, das Messer auch gesehen zu haben.
Bei der Einvernahme vom 3. Dezember 2012 konnte sich die Beschwerdegegnerin an ein Klappmesser mit einem bläulich-grünen Griff erinnern. Gleichentags fand eine Konfrontationseinvernahme statt. Auf die Frage, ob die Person, die sie angegriffen habe, ein Messer in der Hand gehalten oder sie am Hals gepackt habe, antwortete die Beschwerdegegnerin, er habe nur ein Messer gehabt. Mit ihren früheren Aussagen konfrontiert gab sie anschliessend an, die Frage falsch verstanden zu haben.
Am 25. März 2013 sagte die Beschwerdegegnerin aus, der Beschwerdeführer habe das Messer bereits auf der Treppe in den Händen gehalten. Er habe es ihr an den Hals gehalten, nachdem er ihr die Hosen heruntergezogen habe.
An der Hauptverhandlung am 26. August 2013 gab die Beschwerdegegnerin zu Protokoll, der Beschwerdeführer habe sie von hinten um den Hals gepackt und anschliessend kopfvoran die Treppe hinuntergeschleift. Die Füsse seien oberhalb gewesen. Es sei wie ein Schwitzkasten gewesen, der aber so eng war, dass es wie ein Würgen gewesen sei. Sie könne sich nicht erinnern, ob das Messer bereits auf der Treppe oder erst später ins Spiel gekommen sei. Der Beschwerdeführer habe ihr die Tasche nicht entrissen, sondern ihr ein Messer an den Hals gehalten, in ihre Tasche gegriffen und dann das Geld sowie das Mobiltelefon aus der Tasche genommen. Danach habe er sie vergewaltigt. Sie habe das Messer an ihrem Hals gespürt. Auf die Frage, ob sie während des Geschlechtsverkehrs gewürgt worden sei oder ein Messer im Spiel gewesen sei, sagte sie aus, während der gesamten Phase ein Messer am Hals gehabt zu haben. Ob sie in dieser Zeit auch gewürgt worden sei, wisse sie nicht mehr genau.
Die vorinstanzliche Schlussfolgerung, die Aussagen der Beschwerdegegnerin seien äusserst widersprüchlich und zwar sowohl hinsichtlich des Kern- als auch hinsichtlich des Rahmengeschehens, ist unter Berücksichtigung der erwähnten Protokollstellen nachvollziehbar und muss als zutreffend bezeichnet werden. Trotz der Zweifel an den Aussagen der Beschwerdegegnerin erachtet die Vorinstanz ihre Behauptung, sie sei vom Beschwerdeführer in Zusammenhang mit der Wegnahme gewürgt worden, als zutreffend. Ihre diesbezüglichen Thesen sieht die Vorinstanz durch das Gutachten des IRM bestätigt. Allerdings werden im Gutachten, wie vom Beschwerdeführer geltend gemacht, keine eindeutigen Anzeichen eines Würgens erwähnt. So konnten bei der Beschwerdegegnerin keine Einblutungen in den Augenlidern, den Augenbindehäuten oder der Schleimhaut von Mundvorhof und Wangen gefunden werden. Einzig am Hals wurden kratzerartige Hautdefekte festgestellt, die durch eine komprimierende Gewalteinwirkung im Sinne von Kratzspuren entstanden sein könnten. Nach dem von der Beschwerdegegnerin beschriebenen intensiven Würgen, welches bis hin zu Ohnmachtsgefühlen geführt habe, wäre allerdings ein eindeutiger gutachterlicher Befund zu erwarten. Ein solcher wäre zudem erforderlich, um die im Grunde unglaubhaften Aussagen der Beschwerdegegnerin zu relativieren. Ein entsprechender Beweis findet sich auch nicht im Bericht des Kriminaltechnischen Dienstes der Kantonspolizei Bern, worauf der Beschwerdeführer zu Recht hinweist. Demnach wurde am Hals des Opfers keine DNA des Beschwerdeführers gefunden.
Zusammenfassend ist nicht nachvollziehbar, weshalb trotz der im Allgemeinen unglaubhaften Aussagen der Beschwerdegegnerin ausgerechnet das Würgen erwiesen sein soll. Es liegen keinerlei Beweismittel vor, die eine solche Annahme eindeutig bestätigen würden. Selbst wenn man davon ausginge, der Beschwerdeführer habe der Beschwerdegegnerin irgendwann während des Vorfalls an den Hals gefasst oder sie gar gewürgt, lässt sich ein Zusammenhang zwischen dem Würgen und der Wegnahme auch gestützt auf das Gutachten nicht belegen. Die Beschwerdegegnerin selbst erwähnte das Würgen teilweise in Verbindung mit der angeblichen Vergewaltigung und nicht mit der Wegnahme an sich. Bei dieser Beweislage ist die vorinstanzliche Sachverhaltsfeststellung willkürlich, wonach der Beschwerdeführer die Beschwerdegegnerin zum Zwecke der Entwendung ihrer Gegenstände gewürgt habe.
2.
Die Beschwerde ist gutzuheissen. Das angefochtene Urteil ist aufzuheben und die Sache zu neuer Entscheidung an das Obergericht zurückzuweisen. Es sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Beschwerdegegnerin ist keine Parteientschädigung zuzusprechen. Der Kanton Bern hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Die Entschädigung ist praxisgemäss seiner Rechtsvertreterin auszurichten. Damit wird das Gesuch um unentgeltliche Rechtspflege und Verbeiständung gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Das Urteil des Obergerichts des Kantons Bern vom 18. August 2014 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Bern hat der Vertreterin des Beschwerdeführers eine Entschädigung von Fr. 3'000.-- auszurichten.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Bern, Strafabteilung, 1. Strafkammer, schriftlich mitgeteilt.
Lausanne, 7. Oktober 2015
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Schär