{"id":3582,"date":"2023-06-23T18:10:38","date_gmt":"2023-06-23T12:40:38","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3582"},"modified":"2023-06-23T18:10:39","modified_gmt":"2023-06-23T12:40:39","slug":"reverse-string","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/reverse-string\/","title":{"rendered":"Reverse String (C++, Java, and Python)"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach-1-recursion---in-place\">Approach 1: Recursion &#8211; In Place<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#approach-2-two-pointers\">Approach 2: Two Pointers<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#approach-3-using-in-built-functions\">Approach 3: Using in-built functions<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-the-approach\">C++ code for the approach<\/a><\/li><li><a href=\"#java-code-for-the-approach\">Java code for the approach<\/a><\/li><li><a href=\"#python-code-for-the-approach\">Python code for the approach<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-is-the-space-complexity-of-reversing-a-string-using-recursion\">Q.1: What is the space complexity of reversing a string using recursion?<\/a><\/li><li><a href=\"#q2-is-there-some-other-method-to-reverse-the-string\">Q.2: Is there some other method to reverse the string?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a string <strong>S<\/strong>. The task is to reverse the string.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"596\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3761 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-10-1024x596.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-10-1024x596.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-10-300x175.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-10-768x447.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-10-380x221.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-10-550x320.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-10-800x466.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-10-1160x676.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-10.png 1269w\" ><\/figure>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong>S = \u201cFACE\u201d<br><strong>Output: <\/strong>ECAF<br><strong>Explanation: <\/strong>Provided in image above<\/p>\n\n\n\n<p><strong>Input: <\/strong>&nbsp;S = \u201cSCALER\u201d<br><strong>Output:<\/strong> RELACS<\/p>\n\n\n\n<h2 id=\"approach-1-recursion---in-place\"><span id=\"approach-1-recursion-in-place\">Approach 1: Recursion &#8211; In Place<\/span><\/h2>\n\n\n\n<p id=\"the-idea-is-to-use-a-recursive-approach-to-solve-the-problem\">The idea is to use a recursive approach to solve the problem. Observe the below image to understand the approach:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"734\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3762 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-4-1024x734.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-4-1024x734.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-4-300x215.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-4-768x550.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-4-380x272.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-4-550x394.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-4-800x573.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-4-1160x831.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-4.png 1269w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Initialise a <strong>helper<\/strong> function, which consists of two pointers<strong>, left <\/strong>and <strong>right<\/strong> as arguments respectively.<\/li><li><strong>left <\/strong>is initialised to <strong>0<\/strong> and <strong>right<\/strong> to <strong>N &#8211; 1<\/strong>, where <strong>N<\/strong> is the length of the given string.<\/li><li>If <strong>left &lt; right<\/strong>, swap <strong>S[left] <\/strong>and <strong>S[right]<\/strong> and call the helper function of (<strong>left + 1<\/strong>, <strong>right + 1).<\/strong><\/li><li><strong>left &gt;= right<\/strong>, is the base case, hence terminate the loop.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void helper(string s, int left, int right) {\n  if (left >= right) return;\n  char tmp = s[left];\n  s[left++] = s[right];\n  s[right--] = tmp;\n  helper(s, left, right);\n}\n \nvoid reverseString(string s) {\n  helper(s, 0, s.length() - 1);\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> public void helper(char[] s, int left, int right) {\n  if (left >= right) return;\n  char tmp = s[left];\n  s[left++] = s[right];\n  s[right--] = tmp;\n  helper(s, left, right);\n}\n \npublic void reverseString(char[] s) {\n  helper(s, 0, s.length - 1);\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def reverseString(self, s):\n    def helper(left, right):\n        if left &lt; right:\n            s[left], s[right] = s[right], s[left]\n            helper(left + 1, right - 1)\n \n    helper(0, len(s) - 1)<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong>O(N), where N is the length of the string.<br><strong>Space Complexity:<\/strong>O(N), since the recursion stack takes space.<\/p>\n\n\n\n<h2 id=\"approach-2-two-pointers\">Approach 2: Two Pointers<\/h2>\n\n\n\n<p>Another simple approach to solve this problem is to use <strong>two pointers <\/strong>method. One of the pointers is set at the beginning of the string and another at the end. The process is continued, till both the pointers don\u2019t coincide.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"1013\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3764 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-8-1024x1013.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-8-1024x1013.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-8-300x297.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-8-768x760.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-8-80x80.png 80w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-8-110x110.png 110w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-8-380x376.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-8-550x544.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-8-800x791.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-8-1160x1147.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-8.png 1269w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Set <strong>left = 0<\/strong> and <strong>right = N &#8211; 1<\/strong>, where <strong>N<\/strong> is the length of the given string.<\/li><li>While <strong>left &lt; right<\/strong>:<ul><li>Swap <strong>S[left]<\/strong> and <strong>S[right].<\/strong><\/li><li>Move the <strong>left <\/strong>pointer forward and the <strong>right <\/strong>pointer backwards.<\/li><\/ul><\/li><li>Stop the algorithm, when <strong>left == right<\/strong>.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void reverseString(string &amp;s) {\n  int left = 0, right = s.length() - 1;\n  while (left &lt; right) {\n    char tmp = s[left];\n    s[left++] = s[right];\n    s[right--] = tmp;\n  }\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> public void reverseString(char[] s) {\n  int left = 0, right = s.length - 1;\n  while (left &lt; right) {\n    char tmp = s[left];\n    s[left++] = s[right];\n    s[right--] = tmp;\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def reverseString(self, s):\n    left, right = 0, len(s) - 1\n    while left &lt; right:\n        s[left], s[right] = s[right], s[left]\n        left, right = left + 1, right - 1<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong>O(N), where N is the length of the string.<br><strong>Space Complexity:<\/strong>O(1), since no extra space is used.<\/p>\n\n\n\n<h2 id=\"approach-3-using-in-built-functions\">Approach 3: Using in-built functions<\/h2>\n\n\n\n<p>Each programming language has some unique library functions that can perform some specific features.<br>In this section, we will talk about each of those one by one.<\/p>\n\n\n\n<h3 id=\"c-code-for-the-approach\">C++ code for the approach<\/h3>\n\n\n\n<p>In CPP, there is an inbuilt <strong>reverse <\/strong>function in the <strong>algorithm<\/strong> header file, which when accessed can reverse string\/array.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void reverseString(string &amp;s) {\n  reverse(s.begin(), s.end());\n}<\/pre>\n\n\n\n<h3 id=\"java-code-for-the-approach\">Java code for the approach<\/h3>\n\n\n\n<p>In Java, <strong>builtin<\/strong> reverse function can be used by converting the given string to <strong>Stringbuilder. <\/strong>The string class doesn\u2019t have a reverse function.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public void reverseString(String s) {\n  StringBuilder res = new StringBuilder();\n  res.append(s);\n  res.reverse();\n}<\/pre>\n\n\n\n<h3 id=\"python-code-for-the-approach\">Python code for the approach<\/h3>\n\n\n\n<p>Similar to other languages, <strong>Python<\/strong> too has an <strong>inbuilt reverse <\/strong>function, which can be used to reverse a string.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def reverse(string):\n    string = \"\".join(reversed(string))\n    return string<\/pre>\n\n\n\n<p><strong>Practice Question<\/strong><\/p>\n\n\n\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/reverse-the-string\/\" target=\"_blank\">Reverse The String<\/a><\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-what-is-the-space-complexity-of-reversing-a-string-using-recursion\"><span id=\"q-1-what-is-the-space-complexity-of-reversing-a-string-using-recursion\">Q.1: What is the space complexity of reversing a string using recursion?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> The space complexity of reversing string using recursion is O(N) since the recursion stack takes space.<\/p>\n\n\n\n<h3 id=\"q2-is-there-some-other-method-to-reverse-the-string\"><span id=\"q-2-is-there-some-other-method-to-reverse-the-string\">Q.2: Is there some other method to reverse the string?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> Yes, the string can be reversed using many different methods. For example, the string can be reversed using a stack.\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a string S. The task is to reverse the string. Examples: Input: S = \u201cFACE\u201dOutput:&hellip;\n","protected":false},"author":5,"featured_media":3765,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[553],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3582"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3582"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3582\/revisions"}],"predecessor-version":[{"id":20713,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3582\/revisions\/20713"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3765"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3582"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3582"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3582"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}