Sachverhalt:
A.
Die Staatsanwaltschaft Zürich-Limmat stellte das Strafverfahren gegen A._ wegen Diebstahls mit Verfügung vom 8. November 2018 ein. Sie sprach diesem eine Genugtuung von Fr. 200.--, jedoch keine Entschädigung zu.
A._ gelangte dagegen mit Beschwerde an das Obergericht des Kantons Zürich, wobei er ein Schadenersatzbegehren über Fr. 4'200.-- stellte. Das Obergericht trat auf die Beschwerde infolge Verspätung mit Verfügung vom 21. Januar 2019 nicht ein.
B.
A._ beantragt mit Beschwerde in Strafsachen sinngemäss, der Entscheid vom 21. Januar 2019 sei aufzuheben und auf seine Beschwerde sei einzutreten.
C.
Das Obergericht und die Staatsanwaltschaft verzichteten auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt, er habe dem Obergericht am 12. Dezember 2018 per E-Mail eine Übersetzung seiner in polnischer Sprache verfassten Beschwerde zugestellt. In der E-Mail habe er auch darauf hingewiesen, dass er die Papierfassung mit der Originalunterschrift am 10. Dezember 2018 versandt habe. Mit der E-Mail und der Übersetzung durch einen vereidigten Übersetzer sei die Beschwerdefrist gewahrt worden bzw. die E-Mail sei die Grundlage für die Verlängerung der Beschwerdefrist.
1.2. Die Frist für die Beschwerde gemäss <ref-law> beträgt 10 Tage (<ref-law>). Die Frist beginnt am Tag nach der Mitteilung des angefochtenen Entscheids zu laufen (<ref-law>). Sie ist eingehalten, wenn die Beschwerde spätestens am letzten Tag der Frist bei der Strafbehörde abgegeben oder zu deren Handen der Schweizerischen Post, einer schweizerischen diplomatischen oder konsularischen Vertretung oder, im Falle von inhaftierten Personen, der Anstaltsleitung übergeben wurde (<ref-law>).
1.3. Die Einstellungsverfügung vom 8. November 2018 wurde dem Beschwerdeführer am 4. Dezember 2018 an seinem Wohnort in Polen zugestellt. Die 10-tägige Beschwerdefrist begann somit am 5. Dezember 2018 zu laufen und endete am 14. Dezember 2018. Der Beschwerdeführer übergab seine Beschwerde zwar am 10. Dezember 2018 der polnischen Post. Der Schweizerischen Post ging sie jedoch erst am 18. Dezember 2018 zu. Die Beschwerde war daher verspätet.
1.4. Unbegründet ist der Hinweis des Beschwerdeführers auf seine E-Mail vom 12. Dezember 2018. Die Vorinstanz weist zutreffend darauf hin, dass Zuschriften per E-Mail (ohne elektronische Signatur) dem Schriftlichkeitserfordernis von <ref-law> nicht genügen (vgl. Art. 110 Abs. 1 und 2 StPO; <ref-ruling> E. 1.1 S. 301 f.). Daran ändert nichts, dass der Beschwerdeführer seine Beschwerde nicht per E-Mail verfasste, sondern dem Obergericht im Anhang der E-Mail eine beglaubigte Übersetzung seiner in polnischer Sprache verfassten Beschwerde zustellte. Bei der 10-tägigen Beschwerdefrist im Sinne von <ref-law> handelt es sich um eine gesetzliche Frist, die gemäss <ref-law> nicht erstreckt werden kann. Die E-Mail vom 12. Dezember 2018 war entgegen dem Beschwerdeführer daher auch keine Grundlage für die Verlängerung der Beschwerdefrist.
2.
2.1. Der Beschwerdeführer beanstandet weiter, der habe die Einstellungsverfügung vom 8. November 2018 nur in deutscher Fassung erhalten. Ihm sei es faktisch unmöglich gewesen, die 10-tägige Beschwerdefrist einzuhalten, da er auf einen Übersetzer angewiesen gewesen sei, die 10-tägige Beschwerdefrist auch ein Wochenende beinhaltet habe und die Zustellung durch die Post acht Tage dauere. Für die lange Dauer der postalischen Zustellung sei er nicht verantwortlich.
2.2.
2.2.1. Art. 52 Abs. 1 des Schengener Durchführungsübereinkommens vom 19. Juni 1990 (SDÜ) und Art. 16 Ziff. 1 des zweiten Zusatzprotokolls vom 8. November 2001 zum Europäischen Übereinkommen über die Rechtshilfe in Strafsachen (2. ZP zum EUeR; SR 0.351.12) ermächtigen die Justizbehörden der Vertragsparteien, Personen, die sich im Hoheitsgebiet einer anderen Vertragspartei aufhalten, Verfahrensurkunden und Gerichtsentscheidungen unmittelbar auf dem Postweg zu übermitteln. Verlangt wird jedoch, dass die Urkunde - oder zumindest die wesentlichen Passagen - in die Sprache oder in eine der Sprachen der Vertragspartei, in deren Hoheitsgebiet der Empfänger sich aufhält, übersetzt wird, wenn Anhaltspunkte dafür vorliegen bzw. wenn bekannt ist oder Gründe für die Annahme bestehen, dass der Zustellungsempfänger der Sprache, in der die Urkunde abgefasst ist, unkundig ist (Art. 52 Abs. 2 Satz 1 SDÜ; Art. 16 Ziff. 4 i.V.m. Art. 15 Ziff. 3 des 2. ZP zum EUeR). Dass einer beschuldigten Person der wesentliche Inhalt der wichtigsten Verfahrenshandlungen in einer ihr verständlichen Sprache zur Kenntnis gebracht werden muss, ergibt sich auch aus <ref-law>.
2.2.2. Zu übersetzen ist zumindest das Dispositiv des Entscheids sowie die Rechtsmittelbelehrung (vgl. für den Strafbefehl: Urteil 6B_517/2018 vom 24. April 2019 E. 1.3.3 mit Hinweisen, zur Publikation vorgesehen). Eine klare und exakte Belehrung über das verfügbare Rechtsmittel ist für die konkrete Umsetzung der Parteirechte und des Rechts auf ein faires Verfahren unerlässlich. Die Rechtsmittelbelehrung muss der betroffenen Person in einer ihr verständlichen Sprache zur Kenntnis gebracht werden. Ist die betroffene Person der Verfahrenssprache nicht mächtig, muss die Strafverfolgungsbehörde die Rechtsmittelbelehrung in eine für die betroffene Person verständliche Sprache übersetzen, ansonsten diese ihre Verteidigungsrechte nicht wahrnehmen kann. Die Rechtsmittelfrist darf nicht um die Zeit, welche die betroffene Person für das Erhältlichmachen einer Übersetzung benötigt, verkürzt werden (Urteile 6B_667/2017 vom 15. Dezember 2017 E. 5.1; 6B_964/2013 vom 6. Februar 2015 E. 3.3.2).
2.3. Der Beschwerdeführer ist in Polen wohnhaft und befand sich, soweit ersichtlich, nur vorübergehend in der Schweiz. Als Sprache des Beschwerdeführers ist in den kantonalen Akten Polnisch vermerkt. Dieser wurde von der Polizei und der Staatsanwaltschaft (Akten Staatsanwaltschaft, Urk. 2 und 22) jeweils mithilfe eines polnischen Übersetzers befragt. Anhaltspunkte, dass der Beschwerdeführer der deutschen Sprache mächtig ist, liegen nicht vor. Die Vorinstanz hätte diesem daher zumindest die wesentlichen Passagen des Entscheids vom 8. November 2018, d.h. das Dispositiv sowie die Rechtsmittelbelehrung, ev. auch die Erwägung betreffend die Entschädigungsfolgen, übersetzen müssen. Indem sie dies nicht tat, verstiess sie gegen <ref-law> sowie die zuvor zitierten staatsvertraglichen Vereinbarungen. Es erscheint daher überspitzt formalistisch und kommt einem Verstoss gegen den Grundsatz von Treu und Glauben gleich, wenn die Vorinstanz auf die um wenige Tage verspätete Beschwerde nicht eintrat, obschon die Staatsanwaltschaft ihrer Pflicht zur Übersetzung nicht nachkam und die Beschwerdefrist daher um die Zeit verkürzt wurde, welche der Beschwerdeführer für den Erhalt einer Übersetzung benötigte. Die Vorinstanz trat auf die Beschwerde des Beschwerdeführers zu Unrecht nicht ein.
Ob der Beschwerdeführer von der Bestimmung von <ref-law> über den Fristenlauf Kenntnis hatte, ist ungewiss. Offenbleiben kann, ob der angefochtene Entscheid nicht auch deshalb aufzuheben gewesen wäre, weil die Rechtsmittelbelehrung keinen Hinweis auf <ref-law> enthielt (vgl. dazu Urteil 6B_315/2019 vom 5. Juli 2019 E. 1, zur Publikation vorgesehen).
3.
Die Beschwerde ist gutzuheissen, die Verfügung vom 21. Januar 2019 aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Es werden keine Gerichtskosten erhoben (<ref-law>). Dem nicht anwaltlich vertretenen Beschwerdeführer ist keine Parteientschädigung zuzusprechen, da er keine besonderen Verhältnisse oder Auslagen geltend macht, die eine solche rechtfertigen könnten (vgl. <ref-ruling> E. 4b S. 207; <ref-ruling> E. 5b S. 519 f.). Dessen Gesuch um unentgeltliche Rechtspflege ist als gegenstandslos abzuschreiben.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Die Verfügung des Obergerichts des Kantons Zürich vom 21. Januar 2019 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 5. Juli 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Unseld